我試圖計算大O表示法中的一個簡單算法的時間複雜度，但其中一部分嚴重地令我難以理解。這裏是算法的簡化版本：時間整數將循環計數器除以常量的循環的複雜性
int a=n
while(a>0)
{
//for loop with time complexity n^3
a = a/8
}
在這種情況下，它是整數除法，因此while循環將終止的值低於8後，我不知道如何在正方面表示這。我也想知道如何處理像這樣的未來計算，其中循環的數量不太容易定義。
我發現在這種情況下更容易做到這一點。什麼是你在做什麼（甚至大約）？喜歡的東西：
for (a = 1; a <= n; a = a * 8)
{
...
}
現在，我們已經改變了while到for，其中有一個固定的步數，並以遞減遞增，這可能是更容易使用。
我們：
1, 8, 8^2, ..., 8^k <= n
8^k <= n | apply logarithm
log (8^k) <= log n
k log 8 <= log n
=> k = O(log n)
所以while循環執行O(log n)倍。如果你的內部有O(n^3)，那麼你的整個序列將是O(n^3 log n)。
因此，您將循環的條件顛倒過來，以便將其更改爲可以更輕鬆地處理的格式，並且一旦遇到時間複雜性，就會應用逆運算以獲得原始循環的時間複雜度？ –
@ Maria-Andersado不需要任何逆向操作，因爲我改變了你的循環在操作次數方面是等價的，我只是做了相反的操作，以便更容易地推斷步驟的數量。所以它的時間複雜度對應於原始循環的時間複雜度。 – IVlad
這個關鍵是它的整數司，而不是芝諾的悖論。重複的劃分需要log(n)步驟將a減少到在下一步將變爲零的值。
另一種查看二進制整數除法的方法是作爲一個位移。將a向右移動3位，將根據a中最高設置位的位置在幾個步驟後產生一個零點。即(sizeof(a)*CHAR_BIT - leading_zero_count(a))/3。位的位置與log_base2相同。
您需要顯示完整的代碼才能完成此計算。 '//時間複雜度爲n^3的循環是否真的是'n^3'還是真的是'a^3'？有一個很大的不同。總的來說，你需要做的是計算'while'每次迭代需要花費多少時間，以及發生多少次迭代。 –
您是否看到循環執行O（log（n））次？ –