несколько умножений: n(n-1)(n
несколько умножений:
n(n-1)(n-2)=n3-3n2+2n=n3+O(n2)
или, еще точнее,
n3-3n2+2n=n3-3n2+O(n).
На практике оказывается недостаточно "O(nk)-шкалы" для сравнения временнОй сложности алгоритмов. Так, более эффективным, чем алгоритм с линейной трудоемкостью, является его конкурент, чье поведение оценивается как O(log2n). Еще быстрее работает алгоритм с постоянной трудоемкостью - O(1), с одним из них мы уже имели дело - это алгоритм обмена. Соответственно, "между" O(n) и O(n2) находится место для O(n?log2n). Знакомство с такими алгоритмами нам предстоит.
Узнавать о новых алгоритмах и учиться их применять - важная часть программистского образования
Говард Джонстон
Надо сочинить закон или таблицу, по которой числа росли бы необъяснимыми непериодическими интервалами.
Даниил Хармс
Мы столько внимания уделили собственно возможности оценивать временнУю эффективность алгоритма, но пока даже не пытались выяснить, а насколько это нужно практически.
В
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
