算法分析 运行 时间
analysis of algorithm run time
big-O 运行 时间是什么时候?我主要对 while 循环 运行 时间感到困惑。我知道两个 for 循环的 运行 时间都是 O(n)。
cin >> n >> min >> max;
for(int i = min; i < n; i++) {
for(int j = 1; j < max; j++) {
total = 1;
while(total < n) {
total = total *2;
}
}
}
target
在while
循环中的进度是:
1 2 4 8 ... 2^P
您需要 log(2, n)
个步骤 -- 即 n
中的 log
个基础 2
。该循环是 O(log n)
.
首先,你好像忘记戴牙套了。我是你的代码,事实上,整个循环不在嵌套的 for 循环中。实际上,我们有一个无意义的嵌套 for 循环,它只是将 total 设置为 1,然后是一个独立的 while 循环。第一个的复杂度是 O((n - min) * max),第二个是 O(log(n))。总时间复杂度是这些的总和。
可能你真正的意思是这样的:
for(int i = min; i<n; i++) {
for(int j =1; j< max; j++) {
total = 1;
while(total < n) {
total = total *2;
}
}
}
在这里,我们将整个循环放在嵌套的 for 循环中。时间复杂度是我们之前计算的倍数,所以 O((n - min) * max * log(n))。如果 min 和 max 是常量,那么我们可以减少到 O(n log n)
big-O 运行 时间是什么时候?我主要对 while 循环 运行 时间感到困惑。我知道两个 for 循环的 运行 时间都是 O(n)。
cin >> n >> min >> max;
for(int i = min; i < n; i++) {
for(int j = 1; j < max; j++) {
total = 1;
while(total < n) {
total = total *2;
}
}
}
target
在while
循环中的进度是:
1 2 4 8 ... 2^P
您需要 log(2, n)
个步骤 -- 即 n
中的 log
个基础 2
。该循环是 O(log n)
.
首先,你好像忘记戴牙套了。我是你的代码,事实上,整个循环不在嵌套的 for 循环中。实际上,我们有一个无意义的嵌套 for 循环,它只是将 total 设置为 1,然后是一个独立的 while 循环。第一个的复杂度是 O((n - min) * max),第二个是 O(log(n))。总时间复杂度是这些的总和。
可能你真正的意思是这样的:
for(int i = min; i<n; i++) {
for(int j =1; j< max; j++) {
total = 1;
while(total < n) {
total = total *2;
}
}
}
在这里,我们将整个循环放在嵌套的 for 循环中。时间复杂度是我们之前计算的倍数,所以 O((n - min) * max * log(n))。如果 min 和 max 是常量,那么我们可以减少到 O(n log n)