查找涉及 while 循环的运行时函数

Question

我试图为两种不同的算法找到运行时函数和相应的大 O 符号，这两种算法都为堆栈上的每个元素找到跨度。传入的 X 是要计算跨度的列表，传入的 S 是跨度的列表。我想我知道如何找到运行时函数中的大部分内容，一旦我知道那是什么，我就会很好地理解如何使用大 O 表示法。我需要了解的是如何找出所涉及的 while 循环。我认为它们通常涉及对数，虽然我在这里不明白为什么，因为我一直在经历最坏的情况，即每个元素都比前一个大，所以跨度总是越来越大，我看不到与日志的连接.这是我目前所拥有的：

void span1(My_stack<int> X, My_stack<int> &S) { //Algorithm 1
    int j = 0;                                                        //+1
    for(int i = 0; i < X.size(); ++i) { //Find span for each index    //n
        j = 1;                                                           //+1
        while((j <= i) && (X.at(i-j) <= X.at(i))) { //Check if span is larger  //???
            ++j;                                                          //1
        }
        S.at(i) = j;                                                  //+1
    }
}

void span2(My_stack<int> X, My_stack<int> &S) { //Algorithm 2
    My_stack<int> A; //empty stack                                    //+1
    for(int i = 0; i < (X.size()); ++i) { //Find span for each index  //n
        while(!A.empty() && (X.at(A.top()) <= X.at(i))) {               //???
            A.pop();                                                      //1
        }
        if(A.empty())                                                  //+1
            S.at(i) = i+1;
        else
            S.at(i) = i - A.top();
        A.push(i);                                                    //+1
    }
}

span1: f(n) = 1+n(1+???+1)

span2: f(n) = 1+n(???+1+1)

Answer 1

假设所有的栈操作都是O(1):

span1：外循环执行n次。对于从 0 到 n 的每个 i 值，内部循环最多 i 次。因此，总时间与从 1 到 n 的整数之和成正比，即 O(n²)
span2：我们需要以不同的方式考虑这个问题，因为 A 的范围是函数范围的。 A 开始时是空的，所以只能在有东西被推到它上面时弹出，即内部 while 循环只能在调用 A.push 时执行，整个函数的执行时间。但是 A.push 每个外部循环只调用一次，即 n 次 - 所以 while 循环只能执行 n 次。因此整体复杂度为 O(n).

查找涉及 while 循环的运行时函数

finding runtime function involving a while loop

c++

algorithm

big-o

runtime