<分区>
我刚开始使用算法，我试图找出下面 while 循环的“n”形式的运行时间。
int k=1;
while(k<n-k){
k+=k;
}
这里n>2。我知道 k 的值每次都会加倍，并且循环只运行一次，一旦 k 值变得大于 n/2。但我很难用“n”来表达同样的意思。
<分区>
我刚开始使用算法，我试图找出下面 while 循环的“n”形式的运行时间。
int k=1;
while(k<n-k){
k+=k;
}
这里n>2。我知道 k 的值每次都会加倍，并且循环只运行一次，一旦 k 值变得大于 n/2。但我很难用“n”来表达同样的意思。
最佳答案
值得列出要点:
k在每次循环迭代时加倍
您的循环条件可以重写为:while(2*k < n) *
基本问题是:我必须加倍多少次 k , 直到 k doubled 将等于或大于 n ？
这很容易。这正是对数的工作原理。取号2 ， 例如。我必须将它加倍多少次才能达到，比方说，1000？答案是四舍五入的 log21000。
本质上，您的算法是 log_2(n) - 1 ，这意味着您的算法以对数时间复杂度运行。
<子>
*正如 François Andrieux 在他的评论中正确陈述的那样，虽然从数学上讲这个陈述是正确的，但由于数据类型的表示限制，在编程中情况并非总是如此。对于大k s，表达式 2*k可能会导致溢出并使整个表达式无效，而使用相同的输入表达式 k < n-k将表现正确。
关于c++ - 计算while循环的运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52861918/