大O符號檢查理解

我想檢查一下我對Big-O符號的理解。如果我有代碼：大O符號檢查理解

for(int bound = 1; bound <= n; bound *= 2){ 
     for(int i = 0; i < bound; i++) { 
      for(int j = 0; j < n; j += 2){ 
        .....Code 
      } 
      for(int j = 1; j < n; j *= 2){ 
        ......Code 
      } 
     } 
}

是這款N 大O符號？

來源

2014-10-31 Nevets0423

*你認爲什麼？請分享你的想法。 – Maroun 2014-10-31 16:27:20

「for（int j = 0; j 2014-10-31 16:29:27

@markusmalkusch的確。我問他之後。 – Maroun 2014-10-31 17:02:52

不完全。外循環增量爲bound *= 2，因此循環爲O（log n）。兩個內部循環（i和第一個j循環）都是O（n），所以當它們嵌套時它們是O（n ）。（您可以忽略j *= 2內循環，因爲它比j += 2循環更快，也不會顯著有助於程序的運行時間。）

將這個一起，整個程序是爲O（log N * N ）。

來源

2014-10-31 16:35:18

我不完全理解日誌，如果綁定* = 2被綁定/ = 2那也會是日誌 – Nevets0423 2014-10-31 16:42:54

@ user116484如果綁定了/ = 2在第一次迭代之後會綁定什麼？答案：0所以最外層的循環將變成一個無限循環。 – 2014-10-31 16:45:43

@ user116484如果'bound'從'n'開始並且條件是'bound> = 1'，那麼是的，'bound/= 2'也會使該循環在日誌時間內運行。想想循環將運行多少次以獲得不同的n值。它不會運行n次，而是一個非常低的值，接近n的對數。 – 2014-10-31 16:46:19

大O符號檢查理解

回答

相關問題