这个程序的时间复杂度是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;
}
}
最佳答案
整数部分的答案是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)
加上不可压缩的迭代次数,具体取决于机器。
(我为我的回答的经验方面道歉,我不是浮点专家)
关于c - 这个函数的时间复杂度/Big O 是常数吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49264622/