這個while循環的時間複雜度：

Question

這是什麼循環的時間複雜度，因爲它沒有通過1迭代：

while (parser.hasNext()) 
      { 
       token = parser.next(); 

       if (isOperator(token)) 
       { 
        op2 = (String)(stack.pop()); 
        op1 = (String)(stack.pop()); 
        result = evaluateSingleOperator(token.charAt(0), op1, op2); 
        stack.push(result); 
       } 
       else 
        stack.push(token); 
      } 

      return result; 

難道是爲O（n），因爲如果有5個元素，你好，所以循環內的語句將運行5次？

Answer 1

假設大多數操作的典型語義，並假設evaluateSingleOperator（char tokenChar，String op1，String op2）爲O（| op1 | + | op2 |）並返回結果的字符串表示形式，其長度爲結果是O（| op1 | + | op2 |），那麼這實際上具有複雜度O（n^2）。

考慮例如在輸入這個工作： 10 * 10 * 10 * 10 * 10 * 10 * .... * 10

重複乘法幾百次（這樣的結果不只是適合以簡單的整數或長整型值）。然後，您的evaluateSingleOperator（...）調用將隨着輸入的長度線性增長。解析過程本身只需要O（n）次迭代，並且只會調用evaluateSingleOperator O（n）次，但爲了確保總操作時間爲O（n），您需要知道evaluateSingleOperator最多需要O（1）。