找到算法的複雜性

-2

嗨，大家好我明天有一個算法分析考試，我在網上發現了這個問題。我試圖解決這個問題，但我只需要你檢查我的解決方案是正確的找到算法的複雜性

public class t { 
     public static void main(String[] args) { 
     System.out.println(mystery(7, 6)); 
     } 
     public static int mystery(int a, int b) { 
     if (b == 0) return 0; 
     return mystery(a * 2, b/2) + a; 
     } 
    }

我的回答：這個算法有O（LOGN）的複雜性因爲每次b的一半rediced直到我們到達終止條件是1.

來源

2015-10-30 Mira

聽起來對我很好。然而，正如蒂莫西指出的那樣，你需要小心N的定義。例如，如果N是輸入的位數，那麼你的算法實際上是O（N）。（並且一個O（b）算法將是O（2^n）） – hugomg

O（log n）是錯誤的，因爲沒有定義「n」。

雖然我知道你的意思是複雜度是O（log b），這是正確的，但你必須引用正確的變量。否則，假設O（log n）表示O（log a），這將是非常不正確的。

另外，停止條件是b = 0.

來源

2015-10-30 19:02:40

我同意，你有兩個變量a和b，你知道你依賴於一個O符號的情況下，a和b都被假定爲無限因爲神祕（a，b）可以產生任何數字a和b – AGE

'任何數字'？不，這兩個都是整數值，所以我懷疑這個方法可能產生.5，pi或者我爲其他一些數值的數值，因爲它們存在於複數系統中，因此要小心語言。 –

作爲惡魔層還有另一個解決方案如果你在尋找空間複雜度假設尾遞歸的情況下，那麼就是O（1）。 –

找到算法的複雜性

回答

相關問題