если оба алгоритма сортировки выбора и пузырьковой сортировки имеют стоимость O (N2), то почему это не отражено в моем коде?

Question

в моей программе я пытаюсь сравнить алгоритмы сортировки и сортировки пузырьков, однако при сравнении результатов сортировка пузырьков занимает около 10 секунд, чтобы отсортировать рандомизированный массив 10000, а сортировка выбора - 2.

iЯ сравнил мой код с кодом пиров, и это, кажется, не вызвано самой функцией, хотя я не исключил его.

полная программа связана здесь: https://drive.google.com/file/d/1sfOZN_lLBeSmtZJpzmpVjCr5JOeHD9V0/view?usp=sharing

Я ожидаю, что вывод будет немного выше, чем сортировка выбора, но вместо этого он будет намного выше.

Answer 1

Обозначение Big O не эквивалентно времени. Это показатель сложности времени. В качестве примера возьмем следующие фрагменты:

Фрагмент A:

for i in range(n):
   for j in range(n):
      # operation

Фрагмент B:

for i in range(n):
   for j in range(n):
      # operation
   for k in range(n):
      # operation
   for q in range(n):
      # operation

Фрагмент C:

for i in range(n):
   for j in range(n):
      # operation
   for k in range(n):
      # operation
for q in range(100):
   # operation

В фрагменте A операция будет выполняться N^2 раз, в фрагменте B операция будет выполняться 3N^2 раз, а в последнем фрагменте она будет выполняться 2N^2+100 раз; однако, учитывая, что операция имеет O(1), все три фрагмента будут иметь временную сложность O(N^2), но очевидно, что их выполнение не займет одинаковое время.

Посмотрите это информативное видео для получения дополнительной информации.