Есть ли у этого кода квадратичная сложность? - PullRequest
Новая
       11

Есть ли у этого кода квадратичная сложность?

1 голос
/ 14 апреля 2019

Недавно я видел одно решение для следующей алгоритмической задачи:

Учитывая массив целых чисел, вернуть новый массив, где каждый элемент в массив - это число меньших элементов справа от этого элемент в исходном массиве ввода.

например, учитывая массив [3, 4, 9, 6, 1], вернуть [1, 1, 2, 1, 0]

А вот решение в python: 

import bisect

    def smaller_counts(lst):
        result = []
        seen = []
        for num in reversed(lst) :
            i = bisect.bisect_left(seen, num)
            result.append(i)
            bisect.insort(seen, num)
    return list(reversed(result))

Код проблемы.

Авторы этого решения утверждают, что оно имеет сложность O (nlogn), но оно мне кажется некорректным.

А вот мои расчеты по сложности:

В приведенном выше коде функция bisect_right просто выполняет двоичный поиск, поэтому его сложность составляет O (logn) . Давайте посмотрим на исходные коды insort: 

def insort_right(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.
    If x is already in a, insert it to the right of the rightmost x.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    lo = bisect_right(a, x, lo, hi)
    a.insert(lo, x)

def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

Код 1.

Где: 

bisect = bisect_right
insort = insort_right

Код 2.

Очевидно, что insort_right занимает O (n) времени, потому что он выполняет двоичный поиск в начале, который занимает O (logn) времени, а затем вставляет элемент, который занимает O (n) времени.

Теперь давайте взглянем на реализацию функции insert в кодах Python : 

static PyObject *
list_insert_impl(PyListObject *self, Py_ssize_t index, PyObject *object)
/*[clinic end generated code: output=7f35e32f60c8cb78 input=858514cf894c7eab]*/
{
    if (ins1(self, index, object) == 0)
        Py_RETURN_NONE;
    return NULL;
}

static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    Py_ssize_t i, n = Py_SIZE(self);
    PyObject **items;
    if (v == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }

    if (list_resize(self, n+1) < 0)
        return -1;

    if (where < 0) {
        where += n;
        if (where < 0)
            where = 0;
    }
    if (where > n)
        where = n;
    items = self->ob_item;
    for (i = n; --i >= where; )
        items[i+1] = items[i];
    Py_INCREF(v);
    items[where] = v;
    return 0;
}

Код 3

Итак, мы можем заметить, что вставка занимает O (n) времени из-за смещения элементов в static int ins1 (...) . Теперь давайте посчитаем, как это происходит в Код проблемы . Сначала он вызывает bisect.insort (seen, num) , а список seen содержит только один элемент. Во второй итерации увиденное содержит два элемента. Во время n-й итерации список увиденных уже содержит n элементов, поэтому счет операций можно записать так: 1 + 2 + 3 + ... + n - 1 + n , что составляет n (n + 1) / 2 , что составляет O (n ^ 2) . Таким образом, для некоторой i-й итерации требуется O (logn) время для двоичного поиска и O (n) время для вставки (в теле цикла main для цикла). Таким образом, в конечном итоге, сложность для всей проблемы составляет O (n ^ 2) . Верны ли мои расчеты для сложности этой проблемы?

...