시간 복잡도 :

Question

가 1을 반복하지 않기 때문에,이 루프의 시간 복잡도 란 5 개 요소 안녕하세요가 있는지 때문에

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; 

그것은 (n)이 O 될 것이라고 그래서 루프 내부의 명령문이 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

반복 곱셈 몇 번 (그래서 결과는 적합하지 않습니다 단순한 Integer 또는 Long 값). 그런 다음 evaluateSingleOperator (...) 호출은 입력 길이에 따라 선형 적으로 증가합니다.

구문 분석 프로세스 자체는 O (n) 반복 만 필요하며 evaluateSingleOperator O (n) 번만 호출합니다. 그러나 총 작업 시간이 O (n)인지 확인하려면 evaluateSingleOperator는 O (1) 이하 여야합니다.