Сложность времени: теория против реальности

bullbo спросил: 28 марта 2018 в 02:24 в: algorithm

В настоящее время я выполняю задание, которое требует от нас обсуждения временных сложностей разных алгоритмов.

В частности sum1 и sum2

def sum1(a):
    """Return the sum of the elements in the list a."""
    n = len(a)
    if n == 0:
        return 0
    if n == 1:
        return a[0]
    return sum1(a[:n/2]) + sum1(a[n/2:])def sum2(a):
    """Return the sum of the elements in the list a."""
    return _sum(a, 0, len(a)-1)def _sum(a, i, j):
    """Return the sum of the elements from a[i] to a[j]."""
    if i > j:
        return 0
    if i == j:
        return a[i]
    mid = (i+j)/2
    return _sum(a, i, mid) + _sum(a, mid+1, j)

Используя теорему Мастера, мое лучшее предположение для обоих этих типов:

T(n) = 2*T(n/2), которое по Википедии должно соответствовать O(n), если Я не ошибался в своих предположениях, однако, когда я делаю тест с различными массивами длины N со случайными целыми числами в диапазоне от 1 до 100, я получаю следующий результат.

Я попытался запустить тест несколько раз, и каждый раз получаю тот же результат. sum2 кажется в два раза быстрее, чем sum1, что меня озадачивает, так как они должны делать то же количество операций. (?). Мой вопрос в том, являются ли эти algorthim как линейными, и если да, то почему их время выполнения меняется.

Если это имеет значение, я запускаю эти тесты на Python 2.7.14.

2 ответа

Есть решение
EvilTak ответил: 28 марта 2018 в 03:53

sum1 выглядит как O(n) на поверхности, но для sum1 T(n) фактически 2T(n/2) + 2*n/2. Это происходит из-за операций среза списка, которые сами являются O(n) . Используя основную теорему, сложность становится равной O(n log n), что вызывает разницу.

Таким образом, для sum1 требуется время t1 = k1 * n log n. Для sum2, затраченного времени t2 = k2 * n.

Поскольку вы строите график зависимости времени от log n, пусть x = log n , Затем

t1 = k1 * x * 10^x
t2 = k2 * 10^x

с подходящими значениями для k1 и k2 вы получите график очень похожий на ваша. Из ваших данных, когда x = 6, 0.6 ~ k1 * 6 * 10^6 или k1 ~ 10^(-7) и 0.3 ~ k2 * 10^6 или k2 = 3 * 10^(-7).

StriplingWarrior ответил: 30 марта 2018 в 01:23
Я не эксперт по питонам, но этот парень говорит: "Нарезка массивов NumPy возвращает представление, которое разделяет память с оригиналом". Это говорит мне о том, что операции нарезки являются O(1).
EvilTak ответил: 30 марта 2018 в 03:49
@StriplingWarrior, если я не ошибаюсь, спрашивающий, кажется, использует встроенные списки Python, а не массивы. Нарезка списков Python приводит к копированию (операция O(n)), так же, как и в комментарии, который вы указали.
StriplingWarrior ответил: 30 марта 2018 в 09:13
Возможно Вы правы. Я взял тег numpy в сообщении, чтобы обозначить, что он использовал это. Хотя я определенно не в духе Python.
StriplingWarrior ответил: 28 марта 2018 в 02:32

Ваш график имеет log10 (N) на оси x, что означает, что самые правые точки данных соответствуют значению N, в десять раз превышающему предыдущие. И действительно, они занимают примерно в десять раз больше времени. Так что это линейная прогрессия, как вы ожидаете.

bullbo ответил: 28 марта 2018 в 02:41
Я вижу, но почему их время выполнения значительно отличается, разве они не выполняют одинаковое количество операций?
jpp ответил: 28 марта 2018 в 02:47
Тот же порядок сложности не означает то же самое время. Вы можете иметь один и тот же порядок сложности с совершенно разными временами, если операции в каждом случае не одинаково эффективны.
StriplingWarrior ответил: 30 марта 2018 в 01:27
@bullbo: JPP правильно. Алгоритм может занять в 1000 раз дольше, чем другой, и при этом иметь ту же сложность, если при увеличении N он по-прежнему длится только в 1000 раз. Как будет выглядеть ваш график, если вы прислушаетесь к совету Н. Воуды и сделаете свою ось Y логарифмической, и, возможно, увеличите ее еще на одно значение x или два?