大-θ運行時間中的輸入大小N項

Question

而N位整數> 1， A = A/2

我想這是log（n）的，因爲每次都要經過而時間循環你分兩個，但我的朋友認爲它2 logn（n）。

Answer 1

顯然你的算法是大-θ（日誌（一）），其中一個是你的號碼

但據我瞭解你的問題，你想知道的這取決於你的電話號碼

這真的很難說取決於你位數的量漸近運行時間：

比方說你哈ve是一個n位整數，最高有效位是1.你必須將它除以n次，得到一個小於1的數字。

現在讓我們來看一個只有最小siginficant位爲1的整數所以它等於十進制中的數字1）。你只需要一個部門。

所以，我要說，它會採取平均N/2這使得它大-θ（n）的其中ñ是你的號碼的比特量。最壞的情況也大-θ（N）和最好的情況是在大-θ（1）

注：在分裂了一些由兩個二進制系統與十進制系統中十進制數的劃分效果相似

Answer 2

將整數除以二可以通過採用二進制表示法中的數字並移位來有效實現。在最壞的情況下，所有比特的設置必須爲第一個分區移位（n-1）個比特，第二個分步移位（n-2）等等，直到您在最後一次迭代中移位1個比特爲止找到數字等於1，在這一點你停止。這意味着您的算法必須移位1 + 2 + ... +（n-1）= n（n-1）/ 2位，使得算法的輸入位數爲O(n^2)。

一個更有效的算法，將離開a具有相同的值是a = (a == 0 ? 0 : 1)。這會在線性時間內產生相同的答案（相等性檢查在位數上是線性的），它的工作原理是因爲如果a最初爲零，那麼代碼將只保留a = 0;在所有其他情況下，最高位最終在單位的地方。