由循環中 N 的乘法組成的算法的大 O 表示法是什么。void testing(int n) { for(int i =0; i<n;i++) { n=n*2; System.out.println("hi"+n); }}
2 回答
慕絲7291255
TA貢獻1859條經驗 獲得超6個贊
我會盡量嚴謹地回答我的問題。
編輯：忘了說，我們假設比較、賦值和乘法等每個操作的復雜度都是O(1)
簡而言之，該算法在大多數情況下不會終止，因此沒有為其定義復雜度。復雜度是算法成本C的某種上限，說明O(n)復雜度意味著C <= kxn, k > 0。非終止算法的成本是無限的，并且inf > inf是未定義的。
然后，讓我們看看為什么你的算法是非終止的：
每次迭代，如果i < n ，我們繼續。然而，每次迭代n都乘以2。在檢查循環條件時，我們可以看到i和n的值之間的關系： n = n0x2^i，其中n0是n的初始值。因此，您的算法只會在n0 <= 0時終止，并且當這種情況發生時，它不會進入循環一次。
繁花不似錦
TA貢獻1851條經驗 獲得超4個贊
我嘗試在我的 IDE 中運行你的代碼，我發現它是一個無限循環。算法復雜性僅針對算法定義，根據（最常接受的）定義必須終止。當一個程序沒有終止時，它就不是一個算法。所以它沒有“算法時間復雜度”。
添加回答
舉報
0/150
提交
取消