Лучший случай и худший случай времени сложность

Question

Учитывая следующий псевдокод для массива А

x = 0 
    for i = 0 to n - 2 
    for j = i to n - 1 
     if A[i] > A[j]: 
      x = x + 1 
    return x 

наихудший сложность O (N^2) или Theta (п^2) и почему? Кажется, я не понимаю разницы между ними.

Что касается наилучшей сложности случая, разве это не то же самое, что в худшем случае, поскольку алгоритм все еще должен проходить через одни и те же линии?

Answer 1

Доминирующей операцией в этом алгоритме является сравнение A[i] > A[j]. Это сравнение всегда сделано n^2 раз.

O (n^2) означает, что это наихудшая сложность. Если вы используете нотацию O, вы говорите, что эта сложность может быть лучше в лучшем случае.

Theta (n^2) означает, что это сложность в всего корпусов.

Итак, ответ: сложность - это Theta (n^2), потому что в лучшем и худшем случае это n^2.

См: Big-Theta notation и Big-O notation