Блог

Я ищу самую длинную убывающую подпоследовательность целых чисел в массиве. Здесь я использую двоичный поиск (который, как я знаю, называется O (logn)), поэтому я решил, что этот код должен быть O (nlogn). Я попробовал свой код на этом конкретном вводе, и он выполняется за 0,02 секунды. Так вот, я искал в интернете и нашел этот код http://www.geekviewpoint.com/python/dynamic_programming/lds . Автор говорит, что для этого требуется O (n ^ 2), но на моем же входе на выполнение фактически требуется 0,01 секунды, что, очевидно, меньше, чем у моего алгоритма O (nlogn).

 def binary_search(arr, l, r, x):

    while r-l > 1:
        m = l   (r - l) // 2
        if arr[m] >= x:
            r = m
        else:
            l = m
    return r


def longest_decr_subseq_length(array, size):

    table = [0 for i in range(size   1)]

    table[0] = array[n-1]
    length = 1

    for i in range(size - 1, -1, -1):
        if array[i] < table[0]:
            table[0] = array[i]
        elif array[i] > table[length - 1]:
            table[length] = array[i]
            length  = 1
        else:
            table[binary_search(table, -1, length - 1, array[i])] = array[i]

    return length


lis = [38, 20, 15, 30, 90, 14, 6, 17]
n = len(lis)

print(longest_decr_subseq_length(lis, n))
  

Итак, мой алгоритм O (n ^ 2) тоже? Или это нормально, что таково время выполнения? Извините, если вопрос кажется глупым, но я новичок в алгоритмах и все еще немного смущен

Временная сложность не совпадает со временем выполнения. Это означает, что время выполнения будет расти по мере увеличения входных данных. Таким образом, даже при меньшей временной сложности выполнение с тем же объемом данных может занять больше времени, но при увеличении объема входных данных алгоритм с меньшей временной сложностью начнет работать намного быстрее. Что касается сложности вашего алгоритма, ваш расчет кажется правильным, он должен быть O (nlogn)