Какова временная сложность этого алгоритма с наибольшей убывающей подпоследовательностью? - PullRequest
Новая
       22

Какова временная сложность этого алгоритма с наибольшей убывающей подпоследовательностью?

0 голосов
/ 21 апреля 2019

Я ищу самую длинную убывающую подпоследовательность целых чисел в массиве. Здесь я использую бинарный поиск (который я знаю как 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) тоже? Или это нормально, что это время работы? Извините, если вопрос кажется глупым, но я новичок в алгоритмах и все еще немного сбит с толку

1 Ответ

0 голосов
/ 21 апреля 2019

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

...