Почему временная сложность сортировки оболочки не указана в моих данных?

Question

среда: python3.6, Anaconda 5.1, блокнот Jupyter, numba.

Я использовал случайный массив, сгенерированный Python, для измерения временной сложности сортировки оболочки, но обнаружил, что его временная сложность больше соответствуетс NlogN.Я понимаю, что временная сложность сортировки оболочки O (n ^ 2), я в замешательстве.

Код сортировки оболочки:

def shell_sort(list):
    n = len(list)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = list[i]
            j = i
            while j >= gap and list[j - gap] > temp:
                list[j] = list[j - gap]
                j -= gap
            list[j] = temp
        gap = gap // 2
    return list

анализ сложности времени сортировки оболочки

Answer 1

Существует много проблем, связанных со сложностью сортировки в Shell, и есть подозрение, что при некотором подходящем выборе параметров и для некоторых входных данных его сложность может быть O (n.logn).

Answer 2

O (n ^ 2) - это только наихудшая временная сложность, поэтому алгоритм может работать меньше времени, чем на случайном входе и даже в среднем (или даже почти на всех его входах ...).

Кроме того, сложность сортировки Shellsort зависит от выбранной вами «последовательности промежутков» .

Некоторые последовательности промежутков приводят к худшему времени, меньшему, чем O (n ^ 2), напримерO (n ^ 1,5) для последовательности пробелов 1, 4, 13, 40, 121, ... или даже O (nlog ^ 2 (n)) для 1, 2, 3, 4, 6, 8, 9, 12, ... (оба из-за Пратта, 1971).Другими словами: просто попытка ввода одного ввода не имеет никакого значения, и утверждение об O (n ^ 2) может быть ложным в зависимости от точной реализации алгоритма.