懷疑與時間複雜性有關！

考慮下面的代碼片段：懷疑與時間複雜性有關！

for(i = n-1; i >= 0; i--) 
{ 
    if(str[i] == ' ') 
    { 
     i += 2; // I am just incrementing it by 2, so that i can retrieve i+1 
     continue; 
    } 
    // rest of the code with many similar increments of i 
}

說假設循環永遠不會變成成無窮大，如果說我有很多這樣的遞增和遞減循環遍歷，我可以肯定的複雜性就不會是爲了N或N廣場。但是，這種解決方案是否存在廣義的複雜性？

P.S：我知道它了最糟糕的代碼，但還是想給它一個嘗試:-)

來源

2011-03-08 NirmalGeo

因此，我們假設'i'在修改循環的下半部分呢？ – Eric

我看不到你的完整代碼，但我很確定你不能確定運行時間*不在'Theta（N）'中。 – phimuemue

如果字符串中的第一個字符是空格，那麼您需要索引超出數組的範圍。因此，你的程序需要無限的時間來完成算法，因爲它被迫中止！ – Eric

這是一個無限循環（無限複雜性），如果你在你的字符串的空間。由於您使用的是continue，因此它會返回for，並從i + 2開始。

來源

2011-03-08 13:34:05 Aliostad

如果該字符串只包含單個空格，該程序將如何運行無限次數。只有當字符串由所有空格組成時，該程序纔會無限次地運行。如果我是int類型或long類型，它將在達到其最大值後立即變爲負值。 – Algorithmist

這是一個反向循環，'i'從最大值開始，其值遞減。所以當它碰到一個空格時，'i'會增加，所以循環必須從上面的兩個位置開始，它會碰到相同的空間......所以**它永遠不會通過第一個空間。 – Aliostad

假設str在遍歷的過程中沒有改變。

你正在向後遍歷str，當你點擊一個空格時，你將索引向前移動一次，即它會在下一次遞減時再次打開空間，然後再次向前移動它，也就是說你聲稱循環不是無限的，似乎不合理。

來源

2011-03-08 13:42:16 Yasser

如果沒有可變狀態影響i所採用的路徑，那麼要麼進入無限循環，要麼退出n或更少步驟的循環。在後一種情況下，最壞情況下的性能將爲O(N)。

如果循環變異了一些其他狀態，並且該狀態影響了路徑，那麼不理解狀態和變異過程就無法預測複雜性。

（書面，代碼將進入一個無限循環......除非在循環的結尾部分做一些事情，以防止它。）

來源

2011-03-08 13:43:16

懷疑與時間複雜性有關！

回答

相關問題