Временная сложность этого время цикла:

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; 

Будет ли О (п), потому что, если есть 5 элементов, алло, так операторы внутри цикла будут выполняться 5 раз?

Answer 1

Предполагая типичную семантику для большинства ваших операций и предполагая, что оценкаSingleOperator (char tokenChar, String op1, String op2) является O (| op1 | + | op2 |) и возвращает строковое представление результата с длиной в результате получается O (| op1 | + | op2 |), то на самом деле это имеет сложность O (n^2).

Рассмотрим, например, эту работу на входе: 10 * 10 * 10 * 10 * 10 * 10 * .... * 10

Повторите умножение несколько сотен раз (поэтому результат не только подходит в простом значении Integer или Long). Тогда ваши оценочные вызовыSingleOperator (...) будут линейно расти с длиной ввода.

Само по себе процесс синтаксического анализа потребует только итераций O (n), и вы будете ссылаться только на значение sessionSingleOperator O (n), но для того, чтобы обеспечить полное время работы O (n), вам нужно знать, что оценкаСигналОператор требует не более O (1).