java - 算法运行时间

Question

我正在尝试计算以下算法的运行时间。我认为它是 O(n) 因为内循环不依赖于外循环。所以我们可以有 O(n) + O(n) = O(2n) 等于 O(n)它是否正确？我不确定我的逻辑是否正确，我无法弄清楚如何正确分析。

该算法正在寻找元素列表左侧的最大元素。谢谢!

public static void main(String[] args){
    int[] a = {4,3,2,10,4,8,9,1};
    int[] p = new int[a.length];
    ArrayDeque<Integer> previousIndex = new ArrayDeque<Integer>();
    for(int i = 0; i < a.length ; i++){
        while (!previousIndex.isEmpty() && a[previousIndex.peek()] <= a[i]){
            previousIndex.pop();
        }
        if (previousIndex.isEmpty()) { 
          p[i] = 0;
        } else {
          p[i] = previousIndex.peek();
        }
        previousIndex.push(i);
    }
    for(int i = 0; i < p.length ; i++){
        System.out.println(p[i]);
    }
  }
}

Answer 1

这是 O(N)，因为虽然您在循环中有一个循环，但内层循环执行的总次数永远不会超过该循环的总次数

previousIndex.push(i);

被调用，也就是a.length(或N)