Как найти время исполнения в наихудшем случае, используя О-большое?

Question

Какое значение выведет следующая функция?
Ответ должен быть в форме функции числа n.
Найдите время исполнения в наихудшем случае, используя О-большое.

Функция на python:
def F(n):
    r = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            for k in range(i + j - 1, n + 1):
                r += 1
    return r

Я пытался выразить это всё через Σ, однако в некоторых случаях i - j + 1 может быть больше, чем n, из-за этого всё моё решение рушится. У меня была идея в таком случае записать выражение Σᵢ₌₁ⁿ Σⱼ₌ᵢ₊₁ⁿ ((n - i - j + 2) / 2 + |n - i - j + 2| / 2), что брало бы максимум между нулём и n - i - j + 2, однако я не представляю как работать с этим модулем в сумме.

Вот что у меня получилось в первом решении без учёта того, что n - i - j + 2 может быть < 0, если это вдруг как-то поможет: r = (n^2 - n) / 2

Answer 1

Внимательно посмотрим на то, что у нас записано в параметрах цикла и подумаем, как это всё можно привести к одной формуле. Для каждого i от 1 до n есть свой j = i + 1 от i + 1 до n, а для каждого j = i + 1 от i + 1 до n создаётся k = i + j - 1 от i + j - 1 до n. i + 1 и i + j - 1 может быть больше n, тогда цикл не проитерируется.

Чтобы понять, какую формулу тут можно подобрать, построим таблицу Кэли для i и j с операцией i * j = i + j - 1 на примере n = 5:

j = i + 1, поэтому оно начинается минимум с двойки. Также исключаем все случаи, когда i <= j.

Все получившиеся числа больше n = 5 мы вычёркиваем, так как в этом случае итерации по циклу не будет. У нас остаётся меньше половины таблицы со значениями <= 5.

Для каждого начального значения j, например, j = 2, далее цикл проходит до значения n = 5, потом j увеличивается на 1 и проходит от j = 3 до n = 5 (см. на зелёные стрелочки). После того, как первый столбец был полностью пройден, мы переходим ко второму, при этом, столбец становится короче на 1 значение сверху и снизу, в остальном по столбцу происходит такой же подсчёт, как и на предыдущем.

Теперь выведем формулу: Σ ( ((n - 2·i)·(n - 2·i - 1)) / 2, i = 0 to ⌊n / 2⌋ - 1)

Проверим её:

F(5) = 13, (5 * 4 + 3 * 2) / 2 = 13.

F(6) = 22, (6 * 5 + 4 * 3 + 2 * 1) / 2 = 22.

Всё, осталось только привести её к формуле без Σ. Здесь я не буду писать все вычисления, по ответ такой:

F(n) = ((n^2 - n)·⌊n/2⌋ + 2/3 · ⌊n/2⌋·(⌊n/2⌋ - 1)·(2·⌊n/2⌋ - 1) + (⌊n/2⌋ - 1)·⌊n/2⌋ - 2·n·(⌊n/2⌋ - 1)·⌊n/2⌋) / 2

Я проверял её для n от 1 до 500, всё сошлось.

Асимптотика тут примерно F(n) = O(n^3), т.к. в итоговой формуле при раскрытии скобок будет присутствовать член ⌊n/2⌋^3.

БЛОГ НА HUSL

Как найти время исполнения в наихудшем случае, используя О-большое?

Ответы (1 шт):