Задать вопрос

Как вычислять сложность алгоритмов?

What's up, программач.
Любые темы, которые я вижу по алгоритмам, так или иначе касаются их анализа.
Я понял то, что алгоритмы от N log n типа самые быстрые, n^2 медленнее, и там вроде есть просто N и что-то.
Что это это такое вообще? Об этом как то слабо упоминается, и предполагается, что читатель знает эти моменты.

Пример

Предположим, что есть число N, которое равно 1 000 000.Во сколько раз алгоритм с показателем N log N будет быстрее алгоритма с показателем N^2?

Ответ, в 50 000.
Почему?
  • Вопрос задан
  • 14034 просмотра
Подписаться 7 Оценить Комментировать
Пригласить эксперта
Ответы на вопрос 5
IonDen
@IonDen
JavaScript developer. IonDen.com
Начните с цикла статей на хабре Введение в анализ сложности алгоритмов
Ответ написан
Комментировать
@protven
Предположим, что есть число N, которое равно 1 000 000.Во сколько раз алгоритм с показателем N log N будет быстрее алгоритма с показателем N^2?

Ответ, в 50 000.
Почему?

Потому что 1000 000 ^2 / (1000000 * log 1000000) ~ 50000
ВНЕЗАПНО!
Ответ написан
Комментировать
@NgNl
Jira dev
Определить точное время выполнения алгоритма по этой нотации нельзя, дает понятие о масштабе сложности, а не о точном его значении.

O(1) - затраты времени не зависят от размера задачи
O(log(n)) - при увеличении размера задачи вдвое, затраты времени меняются на постоянную величину
O(n) - при увеличении размера задачи в 2 раза, затраты времени возрастут тоже в два раза
O(n^2) - при увеличении размера задачи в 2 раза, затраты времени возрастут примерно в четыре раза
O(n*log(n)) - при увеличении задачи в два раза, затраты времени возрастут в два раза, плюс некоторая прибавка, относительный вклад которой уменьшается с ростом n. При малых n может вносить очень большой вклад. O(n*log(n)) начинает расти как квадрат при малых n, но потом рост замедляется почти до линейного
O(n^p) - полиномиальный алгоритмы, остающиеся мечтой для некоторых задач.
O(a^n), O(n!), O(n^n) - неполиномиальные алгоритмы, в порядке ускорения увеличения затрат времени
Ответ написан
Комментировать
smanioso
@smanioso
Отмечайте ответы на свои вопросы!
Начните со школьного курса математики.
Ответ написан
Vestail
@Vestail
Software Engineer
В данном случае, даже анализ алгоритмов знать не надо, просто разделите N^2/(NlogN) (по основанию 2). А вообще есть стандартные книги типа Кормена и компании. От себя могу порекомендовать Алгоритмы на Java" Роберт Седжвик, Кевин Уэйн, очень хорошо объясняется и море упражнений.
Еще есть несколько курсов на coursera 1, 2.
Ответ написан
Ваш ответ на вопрос

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

Похожие вопросы