gpt4 book ai didi

java - 嵌套 while 循环的大 O 符号解释

转载 作者:塔克拉玛干 更新时间:2023-11-01 21:53:38 24 4
gpt4 key购买 nike

我想知道以下 (java) 代码的大 o 表示法是什么:

while (n > 0) {
while (n > 0){
n-- ;
}
}

如果我使用 n = 10,它将在外循环中执行一次迭代,在内循环中执行 10 次迭代。
那么总共11 次迭代 对吗?
如果我使用 n = 100 它将在外循环中进行一次迭代,在内循环中进行 100 次迭代。
那么总共 101 次迭代 对吗?
但这就是我卡住的地方。因为我认为符号是 O(n)。仅仅是因为我认为迭代几乎等于 n。但是不知道怎么证明?

我不太懂数学,所以需要一个清晰的解释

最佳答案

通俗地说,对于正参数,外循环正好进行一次迭代,因为在内循环中 n 减少到零。内循环将进行 n 次迭代,因此内循环的运行时复杂度为 O(n)。总的来说,虽然外层循环的终止条件在语法上依赖于n,但实际上它独立于n。整体复杂度可以看作是O(n+c),其中c是一个常量,表示外层循环的执行。但是,O(n+c) 等于 O(n)

您可能感到困惑的是,在您的术语中,您说的是一个循环的 101 次迭代,实际上您指的是两个不同的循环。

关于java - 嵌套 while 循环的大 O 符号解释,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39161951/

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