这个函数的时间复杂度/大O是不变的吗？

Question

是这个程序的时间复杂度O(1)？

f1(int n){
  int temp = n;
  while (temp /= 2))
  {
    len++; result+=m;
  }
}

如果我们将int temp改为double temp,那么时间复杂度是否也会改变,或者它会保持不变？

f2(int n){
  double temp = (double)n;
  while (temp /= 2))
  {
    len++; result+=m;
  }
}

Answer 1

整数部分的答案是O(log n)因为每次值都会减半。

double 版本以同样的方式开始，只不过当值达到 1 或接近 1 时，它不会停止并进行除法，直到下溢使其变为 0。此时，除法次数是固定的。

我制作了一个小型的经验校准程序，尝试预测循环数：

#include <stdio.h>
#include <math.h>

void f2(int n){
  int len=0;
  double temp = (double)n;
  while (temp /= 2)
  {
    len++; 
  }
  // 1.53 is an empiric constant, maybe it could be theorically computed
  // it was just to make the numbers match
  printf("%d %lf\n",len,log(n)*1.53+1074);
}
int main()
{

    f2(100000000);
    f2(10000000);
    f2(1000000);
    f2(10000);
    f2(100);
    f2(1);

}

我得到：

1101 1102.183642
1097 1098.660686
1094 1095.137731
1087 1088.091821
1081 1081.045910
1074 1074.000000

因此，复杂性O(log n)加上不可压缩的迭代次数，具体取决于机器。

（我对我的回答的经验方面表示歉意，我不是浮点专家）