c - 这个函数的时间复杂度/Big 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的时候，才停止，直到underflow为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) 加上不可压缩的迭代次数，具体取决于机器。

(我为我的回答的经验方面道歉，我不是浮点专家)