gpt4 book ai didi

algorithm - 依赖嵌套循环的大 O 复杂性

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:07:42 28 4
gpt4 key购买 nike

我能得到一些帮助来理解如何解决这个教程问题吗?我仍然不明白教授的解释。我不确定如何计算第三个/最内层循环的大 0。她解释说,该算法的答案是 O(n^2),并且第二个和第三个循环必须被视为具有 O(n) 的大 0 的一个循环。有人可以用基本的外行术语向我解释第二个/第三个循环的大 O 符号吗假设 n = 2^m

for ( int i = n; i > 0; i --) {     
for (int j =1; j < n; j *= 2){
for (int k =0; k < j; k++){
}
}
}

据我所知,第一个循环有一个 O(n) 的大 O 符号第二个循环 = log(n)第三次循环 = log(n)(因为要循环的次数已经减少了logn)* 2^(2^m-1)(表示增加了j?)

最佳答案

让我们将打印语句添加到最内层的循环中。

for (int j =1; j < n; j *= 2){
for (int k =0; k < j; k++){
print(1)
}
}

输出为

j = 1, 1 1

j = 2, 1 1 1

j = 4, 1 1 1 1 1

...

j = n1 1 1 1 1 ... n+1 次。

问题归结为这将打印多少个 1

那个数字是

(2^0 + 1) + (2^1 + 1) + (2^2 + 1) + ... + (n + 1)

= (2^0 + 1) + (2^1 + 1) + (2^2 + 1) + ... + (n + 1)

= log n + (1 + 2 + 4 + ... + n)

= O(log n + n)

= O(n)


假设您知道为什么 (1 + 2 + 4 + ... + n) = O(n)

关于algorithm - 依赖嵌套循环的大 O 复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54473396/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com