Блог

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

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

например, учитывая массив [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) времени из-за сдвига элементов в статическом 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) времени для вставки (в теле основного цикла for). Итак, в конце концов, сложность для всей проблемы становится O (n ^ 2). Верны ли мои вычисления для сложности этой проблемы?