此while循环的java时间复杂性：

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*....*十,

重复乘法几百次（这样结果就不会只适合简单的整数或长值）。然后您的evaluateSingleOperator（…）调用将随着输入的长度线性增长

解析过程本身只需要O（n）次迭代，您将只调用evaluateSingleOperator O（n）次，但为了确保总操作时间为O（n），您需要知道evaluateSingleOperator最多需要O（1）