Во сколько раз сложность улучшенных сортировок меньше сложности простых?

Question

[Jay Marlow]

Пересмотрел кучу материала по теме, а ответа так и не нашел.
"Простые сортировки имеют сложность порядка N^2, а алгоритмы улучшенных сортировок обладают общей сложностью примерно N*logN."
Из этого тоже не понятно во сколько раз сложность улучшенной меньше сложности простой.

Answer 1

[He11ion]

Эм... N * N / (N * log N) = N / log N раз, очевидно.

Comments

[Jay Marlow]

Тоже так думал, но может есть что-то типа "В 3 РАЗА".

[Леша Киселев]

kolumbou: нет такого

[Kyberman]

Если бы было в 3, или в 5, или в миллион раз, то сложность бы была одинаковая. Сложность оценивает _скорость_ роста.