Как разобрать сложность алгоритма с вложенным циклом?

Question

[Ohurmevshiy]

Читаю книгу "Алгоритмы для начинающих", там есть пример:

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

В книге представлен псевдокод, который я на js написал (пока на ES5):

function simpleStockSpan(arr){  //arr- курсы акций.
    var result = [];
    for(var i = 0; i < arr.length; i++){
        var k = 1;  //Минимальная разница
        var spanEnd = false;
        while( i - k >= 0 && !spanEnd ){
            if(arr[i - k] <= arr[i]){
                k += 1;                
            }
            else{
                spanEnd = true;
            }
        }
    result.push(k);
    }
return result;
}

Я так и не понял, откуда взялось n*(n+1)/2 из 1+2+...+n? За счет чего в два раза увеличено? От количества циклов что ли? Отчего вдруг в "Неочевидности равенства"появилось от 1 до n + от n до 1? Меня реально скосило это объяснение.

Comments

[Zhainar]

Там же есть обьяснение

Answer 1

[Владимир Олохтонов]

"откуда взялось n*(n+1)/2" — это сумма арифметической прогрессии, в книгах по алгоритмам подразумевается, что вы владеете школьной программой по математике.

"откуда появилось от 1 до n + от n до 1?" — оттуда же, это эмпирическое описание формулы суммы арифметической прогрессии: если к первому числу добавить последнее, ко второму предпоследнее и так далее, то сумма каждой пары будет n+1, а всего пар n, значит если все пары сложить, то будет n(n+1), но поскольку здесь мы использовали две суммы от 1 до n вместо одной, то для оригинальной задачи ответ нужно разделить пополам — получим n(n+1)/2.

Всё вышесказанное не отменяет того факта, что подача материала в вашей книге ужасная.

Comments

[igneus fireman]

Всё вышесказанное не отменяет того факта, что подача материала в вашей книге ужасная.

А какую посоветуете?

[Владимир Олохтонов]

igneus fireman, совсем для новичков — "Грокаем алгоритмы", для продвинутых с хорошей математической подготовкой — "Алгоритмы: построение и анализ" Кормэна.