Временная сложность алгоритма с рекурсией

Question

У меня есть следующие:

public static int[] MyAlgorithm(int[] A, int n) { 
    boolean done = true; 
    int j = 0; 
    while(j <= n - 2) { 
     if(A[j] > A[j+1]) { 

      int temp = A[j + 1]; 
      A[j + 1] = A[j]; 
      A[j] = temp; 

      done = false; 
     } 
     j++; 
    } 
    j = n - 1; 
    while(j >= 1) { 
     if(A[j] < A[j-1]) { 
      int temp = A[j - 1]; 
      A[j - 1] = A[j]; 
      A[j] = temp; 
      done = false; 
     } 
     j--; 
    } 

    if(!done) 
     return MyAlgorithm(A, n); 
    else 
     return A; 
} 

Это существенно сортирует массив «A» длины «N». Однако, пытаясь разобраться, какая временная сложность этого алгоритма, я продолжаю сталкиваться с кругами. Если я посмотрю на первый цикл while, содержимое в цикле получит выполнение «n-2» раз, что сделает его O (n). Второй цикл while выполняется в «n-1» раз, что делает его O (n), если мы отбросили константы для обеих функций. Теперь рекурсивная часть этого алгоритма снова отбрасывает меня.

Рекурсия выглядит хвостовой рекурсивной, учитывая, что после этого она не вызывает ничего. На данный момент я не уверен, что рекурсия, являющаяся хвостовой рекурсией, имеет какое-то отношение к этой временной сложности ... Если это действительно O (n), это обязательно означает, что это также Omega (n)?

Пожалуйста, исправьте любые мои предположения, которые я сделал, если они есть. Любые подсказки были бы замечательными!

Answer 1

Это O (n).

Это связано с тем, что при каждой рекурсии вы повторяете весь массив дважды. Когда-то вверх (пузырьковый наивысший ответ на верх) и один раз вниз (пузырьковый самый низкий ответ на дно).

На следующей итерации у вас есть еще 2n. Однако мы знаем, что самые верхние и нижние элементы являются правильными. Из-за этого мы знаем, что у нас есть n-2 несортированных элемента. Когда он повторится, вы будете сортировать еще 2 элемента и так далее. если мы хотим найти число итераций «i», то мы решаем для n - 2i = 0. i = n/2 итераций.

n/2 итерации * 2n операций на итерацию = n операции.

EDIT: tail recursion на самом деле не помогает с временным заказом, но он помогает некоторым языкам с обработкой памяти. Я не могу точно сказать, как это работает, но это значительно сокращает требуемое пространство стека.

Кроме того, я немного ржавый, но обозначение O обозначает случай WORST, тогда как обозначение Omega обозначает BEST-код. Это Omega (n), потому что лучшим случаем является то, что он дважды итерации массива, находит, что все отсортировано, и не рекурсивно.

Answer 2

В вашем случае рекуррентное соотношение это что-то вроде:

Т (п) = Т (п) + п.

Но если мы допустим самый большой номер. закончится в конце каждого случая.Мы можем аппроксимировать:

Т (п) = Т (п-1) + п

Т (п-1) = Т (п-2) + N-1

т (п -2) = Т (N-3) + п-2

Т (п) = Т (п-2) + п-1 + п

Т (п) = Т (п-3) + n-2 + n-1 + n

T (n) = T (nk) + kn -k (k-1)/2

Если пк = 1

то к = п + 1 substitutuing, что

Т (п) = Т (1) + п (п + 1) - (п + 1) (п)/2

порядка O (N^2)

Также наименьшее нет. закончится в начале, так что мы могли бы также приблизиться.

Т (п) = Т (п-2) + п

Еще заказ будет O (N^2)

Если это приближение удаляется мы не можем оценить точно, когда будет сделано будь настоящим. Но в этом случае мы можем быть уверены, что самый большой номер всегда будет заканчиваться в конце после каждой итерации и самого маленького в начале, поэтому ничего не будет сделано для 0 и n-1.

Надеюсь, это поможет вам понять, почему n^2.