Пробег и пространственная сложность этого кода

Question

У меня возникли проблемы с определением большого значения этого решения. Я придумал вопрос CTCI. . Сложность пространства должна быть O (1) , но это время выполнения НА)? Это похоже на O (N^2) из-за цикла while. Но цикл while не запускает N раз для каждого элемента внутри цикла for.

public static int[] missing_two(int [] n){ 

     for(int i=0;i<n.length;i++){ 
      while(n[i]!=i){ 
       int temp=n[i]; 
       n[i]=n[n[i]]; 
       n[temp]=temp; 
      } 
     } 

    } 

Может ли 6,0,1,2,3,4,5 быть примером наихудшего случая здесь? Цикл while будет запускаться n раз по первому индексу. и 0 после этого. Следовательно, это не должно быть O (2n) => O (n)?

Answer 1

Мое понимание состоит в том, что для обозначения верхнего предела или сценария наихудшего сценария используется большая нотация O. Вопрос, который вы должны сделать сами: Может ли вектор ввода n иметь такие значения, что, по крайней мере, в одном случае для всех значений входного вектора n цикл while полностью выполняется? Тогда правильная нотация Big O была бы O (N^2), если бы она не была закрытой, то, по-видимому, O (N^2) была бы лучшей оценкой, чем O (N), так как O (N) для верхней границы были бы уже превышены.

Теперь, когда вы отредактировали этот вопрос и получили больше информации об этом, я согласен с вами. Это O (N)