Является ли большая O времени выполнения моей функции N ^ 2 или N log N?

Question

from linkedlist import LinkedList

def find_max(linked_list): #  Complexity: O(N)
  current = linked_list.get_head_node()
  maximum = current.get_value()
  while current.get_next_node():
    current = current.get_next_node()
    val = current.get_value()
    if val > maximum:
      maximum = val
  return maximum

def sort_linked_list(linked_list):  # <----- WHAT IS THE COMPLEXITY OF THIS FUNCTION?
  print("\n---------------------------")
  print("The original linked list is:\n{0}".format(linked_list.stringify_list()))
  new_linked_list = LinkedList()

  while linked_list.head_node:
    max_value = find_max(linked_list)
    print(max_value)
    new_linked_list.insert_beginning(max_value)
    linked_list.remove_node(max_value)

  return new_linked_list

Поскольку мы повторяем цикл while N раз, время выполнения равно по крайней мере N. Для каждого цикла, который мы вызываем find_max, HOWEVER, для каждого вызова find_max связанный с нами синтаксический анализ списка find_max уменьшается на единицу.элемент.Исходя из этого, разве не время выполнения N log N?

или N^2?

Answer 1

Это n + n-1 + n-2 + ... + 1, что является арифметической последовательностью, поэтому n(n+1)/2. Таким образом, в больших обозначениях O это O (n^2).

Answer 2

Это все еще O(n²); уменьшение размера на 1 каждый раз просто делает эффективную работу n * n / 2 (потому что в среднем вам приходится иметь дело с половиной исходной длины на каждом проходе, а вы все еще делаете n проходов). Но поскольку постоянные коэффициенты не включены в нотацию big-O, это упрощается до O(n²).

Чтобы он был O(n log n), каждый шаг должен был бы уменьшить вдвое размер списка для сканирования, а не просто уменьшить его на единицу.

Answer 3

Не забывайте, O-нотация имеет дело с наихудшей сложностью и описывает целый класс функций. Что касается O-обозначения, следующие две функции имеют одинаковую сложность:

64x^2 + 128x + 256           --> O(n^2)
x^2 - 2x + 1                 --> O(n^2)

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

0th iteration: n
1st iteration: n-1
2nd iteration: n-2
...
nth iteration: 1

Так что вся сложность будет

n + (n-1) + (n-2) + ... + 1  =  n(n+1)/2  =  1/2n^2 + 1/2n

, который все еще O(n^2), хотя это было бы на нижней стороне этого класса.