我的函数的大 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 的每个循环，但是，对于对 find_max 的每次调用，linked_list 我们正在解析到 find_max 减少了一个元素。基于此，运行时不是N log N吗？

还是N^2？

Answer 1

还是O(n²)；每次将大小减少 1 只会使有效工作 n * n / 2（因为平均而言，每次传递都必须处理原始长度的一半，并且您仍在进行 n 传递）。但是由于常数因子不包含在 big-O 符号中，因此简化为 O(n²).

要成为O(n log n)，每一步都必须减半要扫描的列表的大小，而不是简单地减少一个。

Answer 2

是等差数列n + n-1 + n-2 + ... + 1所以是n(n+1)/2。所以在大 O 符号中它是 O(n^2).

Answer 3

不要忘记，O-notation 涉及 worst-case 复杂性，并描述了整个 class 函数。就 O-notation 而言，以下两个函数的复杂度相同：

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)，尽管它会比 class 低。

我的函数的大 O 运行时间是 N^2 还是 N log N？

Is the big O runtime of my function N^2 or N log N?

python

complexity-theory

big-o

python-3.x