計算時間複雜度

Question

需要一些幫助關於如何計算函數的時間複雜度。例如

while(x<N) 
{ 
    while(y<N) 
    { 
     stat 1; 
     if(..) 
      stat; 
    } 
} 

謝謝。

Answer 1

假設x和從0y開始和在每個相應的環由遞增1，它看起來像O（N^2）。

如果你想計算確切的指令數，你應該發佈一些具體的代碼。

Answer 2

如果您是Big O notations的新手，並且有耐心學習最好，請觀看此MIT算法課程的前2個視頻lessons。這是Leiserson自己提供的。

Answer 3

上面的代碼片斷由O（N^2）和下面的一個恆定爲上界...

即當x和y均爲0，並且分別X = Y = N ...