这个函数的大 O 表示法是什么？
What would the big O notation for this function?
以下伪代码的最差时间复杂度大 O 表示法是什么？ （假设函数调用是 O(1)）我对大 O 表示法很陌生，所以我不确定答案，但我在想 O(log(n)) 因为 while 循环参数每次乘以 2还是只是 O(loglog(n))？或者我在这两个方面都错了？感谢任何 input/help，我正在尝试掌握我刚开始学习的最坏时间复杂度的大 O 表示法的概念。谢谢！
i ← 1
while(i<n)
doSomething(...)
i ← i * 2
done
i呈指数增长，因此循环将以对数时间完成，O(log(n))
如果i每次都加倍，那么循环执行的次数就是在达到n之前可以加倍i的次数。或者用数学方法来写，如果 x 是循环执行的次数，我们就有 2^x <= n。求解 x 得到 x <= log_2(n)。因此循环执行的次数是O(log(n))
O(log(n)) 当您想根据数字 n 来说明该算法的时间复杂度时，它是正确的。然而，在计算机科学中，复杂性通常以输入的大小来表示，即位数。那么您的算法将是线性的，即在 O(k) 中，其中 k 是输入大小。
通常，加法等其他运算也被认为是线性的而不是对数的。对数复杂度通常意味着算法不必考虑完整的输入。 （例如二进制搜索）。
如果这是练习的一部分，或者您想讨论计算机科学背景下算法的复杂性，这个区别很重要。
此外，如果真的想学究气：大整数的比较不是常数时间操作，如果考虑通常的整数类型，该算法基本上是常数时间，因为它最多只需要 32或 64 次迭代。
以下伪代码的最差时间复杂度大 O 表示法是什么？ （假设函数调用是 O(1)）我对大 O 表示法很陌生，所以我不确定答案，但我在想 O(log(n)) 因为 while 循环参数每次乘以 2还是只是 O(loglog(n))？或者我在这两个方面都错了？感谢任何 input/help，我正在尝试掌握我刚开始学习的最坏时间复杂度的大 O 表示法的概念。谢谢！
i ← 1
while(i<n)
doSomething(...)
i ← i * 2
done
i呈指数增长，因此循环将以对数时间完成，O(log(n))
如果i每次都加倍，那么循环执行的次数就是在达到n之前可以加倍i的次数。或者用数学方法来写，如果 x 是循环执行的次数，我们就有 2^x <= n。求解 x 得到 x <= log_2(n)。因此循环执行的次数是O(log(n))
O(log(n)) 当您想根据数字 n 来说明该算法的时间复杂度时，它是正确的。然而，在计算机科学中，复杂性通常以输入的大小来表示，即位数。那么您的算法将是线性的，即在 O(k) 中，其中 k 是输入大小。
通常，加法等其他运算也被认为是线性的而不是对数的。对数复杂度通常意味着算法不必考虑完整的输入。 （例如二进制搜索）。
如果这是练习的一部分，或者您想讨论计算机科学背景下算法的复杂性，这个区别很重要。
此外，如果真的想学究气：大整数的比较不是常数时间操作，如果考虑通常的整数类型，该算法基本上是常数时间，因为它最多只需要 32或 64 次迭代。