2011-03-24 115 views
0

我感到困惑與下面的代碼段的時間複雜度....時間以下代碼的複雜性..?

i = 0 

    //first row 
    if(board[i][0] == win && board[i][1] == win && board[i][2] == win) 
     return win; 

    //second row 
    if(board[i+1][0] == win && board[i+1][1] == win && board[i+1][2] == win) 
     return win; 

    //third row 
    if(board[i+2][0] == win && board[i+2][1] == win && board[i+2][2] == win) 
     return win; 

    //first col 
    if(board[0][i] == win && board[1][i] == win && board[1][i] == win) 
     return win; 

    //second col 
    if(board[0][i+1] == win && board[1][i+1] == win && board[2][i+1] == win) 
     return win; 

    //third col 
    if(board[0][i+2] == win && board[1][i+2] == win && board[2][i+2] == win) 
     return win; 

     //first diag 
    if(board[i][i] == win && board[i+1][i+1] == win && board[i+2][i+2] == win) 
     return win; 

    //second diag 
    if(board[i+2][i] == win && board[i+1][i+1] == win && board[i][i+2] == win) 
     return win; 
+3

我是一個循環的一部分還是隻是總是0? – BrandonAGr 2011-03-24 04:55:35

回答

3

這顯然是一個陷阱問題,看看你是否理解時間複雜性的概念。

時間複雜度衡量算法在應用於更大和更大輸入時所需的數量級。你的例子只依賴於一個常數的輸入,這就是爲什麼其他人正確地說O(1)。實質上,這意味着時間複雜性不是衡量其效率,質量或者其他任何方面的正確工具。

4

它將在恆定時間,即ø運行(1)假設板[M] [N]是二維陣列。

3

O(1) - 沒有迭代和遞歸。

1

正如其他答案所示,它是O(1)。但這不被認爲是良好的編碼習慣。你可以使用循環來概括它。

0

正如你在那裏展示的那樣,它是O(1),因爲它沒有可變的方面。它總是需要相同的時間來執行。

如果你把它放在一個從0到n-1的循環中,那麼它將有O(n),即線性複雜度。如果你將n的大小加倍,那麼執行時間大約會增加一倍。