操作n對演算法的 O 有影響嗎？
遞回代碼例如：
Public void Foo(int n)
{
n -= 1;
if(n <= 0) return;
n -= 1;
if(n <= 0) return;
Foo(n)
}
是否重新分配n影響O(N)？對我來說聽起來很直觀......
這個演算法有沒有O(N)通過丟棄常數？從技術上講，由于它遞減n2，因此它不會具有與以下相同的數學效果：
public void Foo(int n) // O(Log n)
{
if(n <= 0) return;
Console.WriteLine(n);
Foo(n / 2);
}
但是，既然您只觸及了一半的金額，那么n貢獻的減半難道不是嗎？需要明確的是，我正在學習 O Notation 和它的微妙之處。我一直在尋找類似于第一個示例的案例，但我很難找到這樣一個具體的答案。O(N)n
uj5u.com熱心網友回復：
在談論 O 表示法時，重新分配 n 本身并不是真正重要的。例如，考慮一個簡單的 for 回圈：
for i in range(n):
do_something()
在這個演算法中，我們做了 n 次。這將等效于以下演算法
while n > 0:
do_something()
n -= 1
并且等效于您提供的第一個遞回函式。所以真正重要的是與輸入大小（即 n 的原始值）相比完成了多少計算。出于這個原因，所有這三種演算法都是 O(n) 演算法，因為它們每次都將“輸入大小”減小一。即使他們將其增加了 2，它仍然是一個 O(n) 演算法，因為在使用 O 表示法時常量并不重要。因此，以下演算法也是 O(n) 演算法。
while n > 0:
do something()
n -= 2
要么
while n > 0:
do_something()
n -= 100000
但是，您提供的第二個遞回函式是 O(log n) 演算法（即使它沒有基本情況，并且在技術上會一直運行到堆疊溢位），正如您在評論中所寫的那樣。直觀地說，當每次將輸入大小減半時，會發生什么，這恰好對應于以原始輸入數的以二為底的對數。考慮以下：
n = 32。演算法每次減半：32 -> 16 -> 8 -> 4 -> 2 -> 1。我們總共進行了 5 次計算。等效地 log2(32) = 5。
回顧一下，重要的是原始輸入大小以及與此輸入大小相比完成了多少計算。任何可能影響計算的常數都無關緊要。
如果我誤解了您的問題，或者您有后續問題，請隨時評論此答案。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446407.html