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