輸入。兩個n位整數x和y，其中x≥0，y≥1。
輸出。x除以y的商和余數。
如果x=0，則回傳（q，r） :=（0，0）。
q :=0；r :=x。
如果(r≥y)做
{ q := q 1;
r := r - y}。
回傳（q, r）。
我得到的大O復雜度是O(n^2)，但一個朋友說它是O(2^n)，其中n是作為輸入大小的位元數
。請提供解釋
。uj5u.com熱心網友回復：
while-loop的迭代次數正好是floor(x/y)。每個迭代需要n操作，因為這就是減法的復雜性r - y。
因此，該演算法的復雜性是n * floor(x/y)。然而，我們希望將復雜性表達為n的函式，而不是x和y的函式。
因此問題變成了：在最壞的情況下，floor(x/y)與n的關系如何？
當x和y是兩個非負的n位數，并且y >=1時，可以得到的x/y的最大值是取x的最大可能值和y的最小可能值。
-
的最大可能值是
y的最小可能值是y=1。
x = 2**n - 1（x的所有位在其二進制表示中是1）；
因此，x/y的最大可能值是x/y=2**n-1。
你的除法演算法的時間復雜度是O(n * 2**n)，當x = 2**n - 1和y = 1時，這個上界就實作了。
uj5u.com熱心網友回復：
我提議的解決方案：
當計算大O復雜度時，我們需要取n->無窮大，其中n是>輸入大小，我們有3種 可能性：
- x & y
- 當n->無窮大時，x & y都變成無窮大
- 當n->無窮大時，y變成無窮大
。- 當n->無窮大時，x變成無窮大
。我們這里只對情況3感興趣，
(x-i * y ) < y，i是迭代次數
也可以寫成x/y < i 1
當x變成無窮大時，LHS(左手邊)在這個方程中是無窮大的。 方程中，這意味著RHS也是無窮大的
因此，當n-&y < i 1
在這個方程中，LHS（左手邊）是無窮大的。
因此，當n->無窮大時，迭代的次數就等于n
因此，復雜度是O(n^2)
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/332565.html
標籤：