@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;
}

5d0530b252c4a033399456.jpeg
Я так и не понял, откуда взялось n*(n+1)/2 из 1+2+...+n? За счет чего в два раза увеличено? От количества циклов что ли? Отчего вдруг в "Неочевидности равенства"появилось от 1 до n + от n до 1? Меня реально скосило это объяснение.
  • Вопрос задан
  • 113 просмотров
Решения вопроса 1
sgjurano
@sgjurano
Разработчик
"откуда взялось n*(n+1)/2" — это сумма арифметической прогрессии, в книгах по алгоритмам подразумевается, что вы владеете школьной программой по математике.

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы