Y
Ну фраза thetha n log n и фраза асимптотическая сложнонсть алгоритма n log n - это одно и тоже
Size: a a a
2021 May 16
A
а, ну это просто для понимания надо говорить в терминах асимптотического анализа и анализа бесконечно малых, но мне не кажется это хорошей затеей в инженерном кругу.
A
позволю себе картинку из вики для перевода одного в другого, если вдруг кто решит почитать
Y
В общем я ща правда открыл и почитал все что есть в интернетах и пишут очень плохо и непонятно
AR
ура, матан! )
A
ну из определения если мы получили оценку Theta лучше чем у нас была О-большое, то нам следует ее и использовать
A
но для classic qsort оценка n^2
Y
Потому что если функция qSort Thetha(nlogn) ограничевает сверху, то можно сделать неправильный вывод о том что она O(nlogn)
Y
Ага, как раз про это и говорю
Y
И n log n достигается за счет рассчета функции сложности для всех перестановок входных данных
A
вот это я сейчас не понял 🙂
Y
qsort работает линейно для некоторых наборов, например скорость сортировки упорядоченного массива будет n
Y
А инвертированнного n^2
A
да
A
bigO(n^2), bigOmega(n)
Y
И теперь если посчитать эту функцию для всех n! Вариантов и разделить на n! То получится замечательный предел из которого и выйдет это log n
Y
В моей голове эта математика так сходилась
A
неа
A
Это не статистический анализ, а просто анализ функций.