歐幾里德的GCD空間複雜度算法

這似乎是一個愚蠢的問題，但是歐幾里得的GCD算法O（1）在迭代實現中的空間複雜度？我只是想確認（在谷歌上找不到）歐幾里德的GCD空間複雜度算法

2016-03-25 a_123

是的，你只需要一個臨時變量或兩個，不依賴於輸入，所以它是O（1）。

2016-03-25 22:19:32 maniek

Thanks :)如果我們做遞歸實現，空間複雜度是O（logn），其中n是兩個數中較大的那個？ –

@ s_123它是O（日誌（較小號碼））。這一切都假設算術運算需要恆定的時間/空間。如果我們使用1000位數字，這不一定是真的。 – maniek

爲什麼你說它的O（日誌（較小數字））？正如我看到算法一樣，每兩次迭代中更大的數量減少至少一半。所以我說它的O（日誌（更大的數字））。我看不出爲什麼它可以是O（日誌（較小的數字））。 –

回答