找出一个简单打印函数的估计值
找出一个简单打印函数的估计值
提问于 2014-02-18 14:43:23
while (num > 1)
{
cout << "num is now " << num << endl;
cout << "hello // \n";
num /= 2;
}我正试图给出打印报表的大O值。
用户可以输入num。我尝试了一些输入，并开始看到一个模式。
- 1表示0的打印。
- 2-3给出1个打印。
- 4-7给出2个指纹。
- 8-15分出3个指纹。
- 16-31给出4张指纹。
让p = the number of prints。我看到给你一定数量的指纹的数字范围是2^p。
那么大的O估计值是2^p吗？
回答 2
Stack Overflow用户
发布于 2014-02-18 14:52:21
我是O(log N)。原因是每次迭代将范围减半。如果您熟悉二进制搜索，那么如果您做类似的事情，那么您的循环。
您正确地观察到了2^p模式。与此相反的是log base-2 (而不是log base-10)。当人们在大O符号中提到log时，他们通常指的是基-2版本。
Stack Overflow用户
发布于 2014-02-18 15:02:29
只需使用主定理。
链接在这里
B=2f(N)=1a= 1。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/21857142
复制相关文章
相似问题
腾讯云开发者
