Анализ время выполнения вложенной для алгоритма петель

Question

сказать, что я следующий код

def func(A,n): 
    for i = 0 to n-1: 
    for k = i+1 to n-1: 
     for l = k+1 to n-1: 
     if A[i]+A[k]+A[l] = 0: 
      return True 

А представляет собой массив, а п обозначает длину А.

Как я прочитал, код проверяет, имеются ли какие-либо 3 последовательных целых числа в сумме A до 0. Я вижу временную сложность как

T (n) = (n-2) (n-1) (n-2) + O (1) => O (n^3)

Правильно ли это, или я что-то упускаю? Мне трудно найти материал для чтения об этом (и у меня есть CLRS)

Answer 1

У вас есть неправильная функциональность: он проверяет, не связаны ли какие-либо три элемента до 0. Чтобы улучшить время выполнения, он учитывает их только в индексе заказ: i < k < j.

Вы в точности относитесь к сложности. Хотя каждый цикл занимает короткое замыкание, этот короткий отрезок является просто скалярным делителем числа итераций. Каждый цикл по-прежнему O (n).

Что касается кодирования, то у вас уже есть большая часть его - и переполнение стека не является кодировкой. Дайте ему ваш лучший выстрел; если это не работает, и вы застряли, задайте другой вопрос.

---

Если вы действительно хотите научить себя новую технику, посмотреть itertools пакет Python. Вы можете использовать это для создания всех комбинаций в тройках. Затем вы можете просто проверить сумму (тройную) в каждом случае. Фактически, вы можете использовать метод any, чтобы проверить, не имеет ли какая-либо тройная сумма до 0, что может уменьшить ваше тело функции до одной строки кода Python.

Я оставлю это исследование вам. Вы узнаете о других аккуратных вещах в пути.

---

Дополнение для комментария ОП.

Зададим N 4, и посмотреть на то, что происходит:

i = 0 
for k = 1 to 3 
    ... three k loop 
i = 1 
for k = 2 to 3 
    ... two k loops 
i = 2 
for k = 3 to 3 
    ... one k loop 

Число выполнений к-петлевых является "треугольник" количество п-1: 3 + 2 + 1. Пусть м = n-1; формула T (m) = m (m-1)/2.

Теперь вы распространяете ту же логику на петли l. Вы запускаете петли T (k) на l для k = 1, 2, 3. Если я помню, эта формула «пирамиды» третьего порядка представляет собой P (m) = m (m-1) (m-2)/6.

В терминах n это (n-1) (n-2) (n-3)/6 петель на l. Когда вы умножаете это, вы получаете прямую формулу куба в n.

Вот последовательность при п = 5:

0 1 2 
0 1 3 
0 1 4 
    change k 
0 2 3 
0 2 4 
    change k 
0 3 4 
    change k 
    change k 
    change l 
1 2 3 
1 2 4 
    change k 
1 3 4 
    change k 
    change k 
    change l 
2 3 4 

BTV, л является плохим именем переменным, легко спутать с .