Найти инвариант цикла в программе для вычисления сумм кубов?

Question

Я не уверен на 100%, что такое инвариант тройного степенного суммирования.

Примечание: n всегда является неотрицательным значением.

Псевдокод:

triplePower(n)
    i=0
    tot=0
    while i <= n LI1
        j = 0
        while j < i LI2
            k = 0
            while k < i LI3
                tot = tot + i
                k++
            j++
        i++

Я знаю, что это грязно и может быть сделано гораздо проще, но этоэто то, что я должен делать (в основном для практики анализа алгоритмов).

Я должен придумать три инварианта цикла;LI1, LI2 и LI3.Я думаю, что для LI1 инвариант имеет какое-то отношение к tot = (i ^ 2 (i + 1) ^ 2) / 4 (уравнение для суммы кубов от 0 до i)Я не знаю, что делать для LI2 или LI3.Цикл в LI2 делает i ^ 3, а LI3 делает i ^ 2, но я не совсем уверен, как определить их как инварианты цикла.

Было бы легче определить инварианты, если бы у меня было 3 отдельных суммарных переменныхв каждом из тел цикла while?

Спасибо за любую помощь, которую вы можете оказать.

Также есть порядок роста этой функции: Θ (n ^ 3)?

Answer 1

Когда сталкиваешься с подобным циклом, который вычисляет сумму постепенно, хорошим инвариантом для поиска является то, равна ли общая сумма, которую вы вычислили до сих пор, первой части суммы, которую вы считаете такой. В этом случае вы хотите вычислить сумму первых n положительных совершенных кубов и сделать это, добавляя в кубы по одному за раз. Таким образом, одним из возможных инвариантов будет то, что

tot = sum (j переходит от 0 к i) j ³

Кроме того, какова связь между i и n? Ну, наверное, у нас должно быть это n + 1. Почему n + 1? Это потому, что на последней итерации, когда i = n, мы все равно увеличиваем i. Используя эти два инварианта, вы можете доказать, что этот цикл вычисляет правильное значение.

Что касается времени выполнения, вы можете вычислить это довольно легко. Во-первых, сколько работы выполняется на каждой итерации? O (1)? На)? О (п ² )? Тогда сколько существует итераций цикла? O (1)? На)? О (п ² )? Произведение этих двух терминов даст вам ответ.

Надеюсь, это поможет!

Answer 2

Ваш алгоритм может быть упрощен следующим образом (надеюсь, вы привыкли к синтаксису языка C):

tot = 0;
for ( i = 0 ; i <= n ; i ++ )
    for ( j = 0 ; j < i ; j ++ )
        for ( k = 0 ; k < i ; k ++ )
            tot = tot + i;

И затем вы можете перевести его в сигма-нотацию: