这个函数的复杂性？
void compute(int n) {
int h = n;
while (h > 1) {
for (int i = 0; i < n; i++) {
// do some operation
}
h = h / 2;
}
}
谁能告诉我 n 的这个函数的复杂度（大 O ）是多少？
这其实是我和我一个朋友之间的争论。 我的立场：复杂度是 O(n*log(n)) 朋友的立场：log(n)
感谢您的回复。
void compute(int n) {
int h = n;
while (h > 1) {
for (int i = 0; i < n; i++) {
// do some operation
}
h = h / 2;
}
}
Can anybody please tell me what is the complexity( Big O ) of this function of n ??
This is actually an argument between me and a friend of mine.
my stand: complexity is O(n*log(n))
friend's stand: log(n)
Thanks for your responses.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
我想说，因为在每次运行中，h 都会减半并且完成 n 次操作，所以它的时间复杂度为 O(n * log n)。
I'd say since in every run, h is halved and n operations are done, it's O(n * log n).
如果这是家庭作业（听起来有点像），那么你应该先自己尝试一下。
基本上，为了获得复杂性，您可以查看函数的结构，即循环、嵌套循环等，并确定它们运行多长时间、它们依赖哪些输入等。
在这种情况下，您只有一个输入， n。局部变量 h 以与 n 相同的值开头，因此从复杂性角度来看，它本质上是相同的，但是，您需要跟踪它的使用方式。
这里本质上有两个嵌套循环，一个运行到n，另一个围绕它运行，导致h每次运行时减半。所以这个函数的时间复杂度为 O(n · log2n)。
If this is homework (and it sounds a bit like it), then you should first try yourself.
Basically to get the complecity you look at the structure of the function, that is loops, nesting loops, etc. and determine how long they run, which inputs they depend on, etc.
In this case you have only one input, n. The local variable h starts with the same value as n, so it's essentially the same, complexity-wise, however, you need to keep track of how it's used.
You have essentially two nested loops here, one that runs to n, another one around it, that causes h to halve each time it's run. So this function is in O(n · log2n).
一些操作：
for 循环：因为 n >= h 且
假设 h 在“某些操作”期间不会被修改：
外部 while 循环：
Some operation:
The for loop: because n >= h and
supposing h will not be modified during "some operation":
The outer while loop:
看起来是O(n.sqrt(n))
外层循环显然是n，内层循环是sqrt(n)。
编辑：内部循环正确为 log(n)，因为迭代次数为 x，其中 2^x = n。
It appears to be O(n.sqrt(n))
The outer loop is obviously n, and the inner loop is sqrt(n).
EDIT: The inner loop is correctly log(n), because the number of iterations is x where 2^x = n.
显然是n*log(h)。
It is clearly n*log(h).