Время выполнения алгоритма

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

Чтобы определить порядок, вы действительно смотрите на наихудший случай. Вы правы, что вложенная петля является причиной для беспокойства здесь:

for(int i = 0; i < a.length ; i++){ 

Это сразу же заказать N

while (!previousIndex.isEmpty() && a[previousIndex.peek()] <= a[i]){ 

Это потенциально может также пойти почти N раз.

Таким образом, окончательный порядок N*N или N^2

Вы должны иметь в виду обычное дело, хотя. Если вполне вероятно, что цикл while фактически выйдет после всего лишь нескольких итераций, вы можете вернуться к O(N).

Answer 2

На самом деле, вы в порядке и имеете алгоритм O (N), но это сложнее доказать, чем большинство. Это предполагает, однако, что .isEmpty(), .peek() и т. Д. На ArrayDeque - все операции с постоянным временем. Проконсультируйтесь с документацией.

Ключ в том, что ваша обработка deque во внутреннем цикле разрушительно:

while (!previousIndex.isEmpty() && a[previousIndex.peek()] <= a[i]){ 
    previousIndex.pop(); 
} 

Это удаляет элемент из previousIndex каждый раз, и может работать только тогда, когда есть один, чтобы удалить. Таким образом, всего количество циклов while может работать по всем индексам, это количество раз, которое что-то .push ed в deque. И так как это происходит только в одной точке - в конце первого цикла for - мы можем видеть, что количество нажатых элементов - O (N).

Answer 3

Это O (N) для хотя у вас есть цикл внутри цикла, общее число раз, когда внутренний цикл будет выполняться никогда не может быть больше, чем общее число раз, когда

previousIndex.push(i); 

является (или N)