Итак, что действительно заставило меня споткнуться здесь, так это то, что когда я пытался вычислить временную сложность этого алгоритма, меня смутил тот факт, что есть 3 цикла, которые заставили бы меня поверить, что операции O (n ^ 3), но дело в том, что средняя петля уменьшается по мере увеличения внешней петли, а самая внутренняя петля увеличивается по мере уменьшения средней петли. Я бы предположил, что это общий алгоритм O (n ^ 2), но он все еще кажется O (n ^ 3) из-за 3 вложенных циклов. При подсчете количества операций во время выполнения кода я получаю подсчет где-то между O (n ^ 2) и O (n ^ 3), что еще больше разочаровывает...
Я что-то пробовал, хотелось бы услышать какие-то исправления, прошло некоторое время с моего курса алгоритма :)
The Sigma is for every loop. notice how it's becoming a multiply when there is no dependency on the variable
В этом посте было действительно хорошо сказано, чтобы понять концепцию, которая была основной целью поста, я полагаю, что большинство людей поймут последний шаг, и поэтому я назначу это как ответ. Огромное спасибо за помощь!
Последний шаг кажется неправильным:
Sigma (n-d)(d+1) = n Sigma (d+1) - Sigma d(d+1)
. Первый член равен(n^3)/2
, второй —(n^3)/3
, и кубики не обращаются в нуль.