Блог

У меня есть фрагмент кода. Я думаю, что сложность кода равна O (n). Но не уверен, поэтому, пожалуйста, подтвердите меня?

 int low=0;
int high=array.length-1;

while(low<high)
    {
        while(array[low]!=0)
            low  ;
        while(array[high]==0)
            high--;

        int temp=array[low];
        array[low  ]=array[high];
        array[high--]=temp;
    }
 

Ваша программа продолжает увеличиваться до минимума и уменьшаться до максимума, пока они не встретятся, так что это O (n)

Ваша программа представляет собой алгоритм слияния, который равен O (N) или линейному времени.

В конце вашей программы количество раз, которое вы увеличиваете low , плюс количество раз, которое вы уменьшаете high , будет длиной массива, которая равна O (N).

Известный алгоритм с аналогичной структурой — это шаг разделения в Quicksort. Возможно, вы сможете найти более подробный анализ, если поищете это.

O (n)

Вы можете запутаться с O (n ^ 2), но поскольку вы можете заменить while на if условия, тогда не будет 2 циклов, а циклы просто помещаются туда для увеличения вычислений.

вы также можете сделать следующее:

 while(low<high)
{
    if(arr[low]!=0)
        low  ;
    if(arr[high]==0)
        high--;
    //Rest of the things
}
 

Здесь очевидно, что сложность равна O (n), и код точно такой же. Таким образом, ваш код также имеет сложность O (n).

Не обязательно
, если все в {} равно O (1), тогда да, это O (n)

 int low=0;
int high=array.length-1;
while(low<high)
{
}
 

Если бы что-то в {} было O (n), то это было бы порядка n в квадрате