A
определение Theta на картинке выше. Поэтому утверждение что BigTheta (n log n) есть асимптотика classic qsort я нахожу ложным
Size: a a a
2021 May 16
Y
Ну я же могу сделать функцию которая заведомо всегда будет n^2 и она будет расти быстрее nlogn
Y
Всегда запихивать массив задом наперед вне зависимости от n.
Из чего можно сделать вывод(один или несколько):
- для оценки алгоритмов используется что-то другое
- тетта расчитывается как-то иначе
- qsort не тетта нлогн
Из чего можно сделать вывод(один или несколько):
- для оценки алгоритмов используется что-то другое
- тетта расчитывается как-то иначе
- qsort не тетта нлогн
A
и bigOmega по-моему nlog2n
СА
Это микс из ошибки выжившего и самосбывающегося пророчества. Если делать джунами из говна и палок - то точно не проживёт больше года.
A
https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort ну вот как они размышляют 🙂 при анализе
A
мне просто сложно принять их концепт, потому что это уже не матиматика. Типа ну вот есть плохой случай, но мы на него в целом забьем, потому что вероятность мала.
Y
Ну вот тоже хороший вопрос, как этот эвередж считается. С массивом еще можно понять, а вот с операцией put в хэш таблицу какую-то на листе бакетов которая сделана - там уже вообще не понятно как считать ‘вероятности’
A
Ну по мне лучше иметь грубую оценку, но без допущений и отталкиваться от нее.
Y
Тогда стандартом была бы пирамидальная сортировка
A
Но я больше функциональным анализом позанимался. Там недопустимо исследовать функции на части области определения 😅
A
Аххха. Вот да. Практика от статей далеко...
СА
Замечательный номер откалывает мне тут в прямом эфире 11-я постгря. Есть вполне пристойного размера таблица: 100м записей, 20 гигов с индексами, смешно по меркам XXI века. Автоинкрементный id BIGINT и индекс по текстовой колонке. Если я запрашиваю несуществующее значение из текстовой колонки - мгновенно отдаёт пустой ответ. Если запрашиваю его же, но при этом заказываю сортировку по id задом наперёд (то есть хочу последние N записей, если найдутся) - фигачит реверсный фуллскан по ПК, игнорируя индекс по текстовому полю.
На вопрос "как дать пострге намёк, что надо использовать именно текстовый индекс" ответ "никак, много вас тут таких умных ходит, нам виднее, какие индексы использовать".
И эти люди смеются над Монгой!
На вопрос "как дать пострге намёк, что надо использовать именно текстовый индекс" ответ "никак, много вас тут таких умных ходит, нам виднее, какие индексы использовать".
И эти люди смеются над Монгой!
SG
Сдерживаюсь, чтобы не форварднуть Олегу Бартунову в личку :)
СА
EXPLAIN SELECT * FROM table WHERE name='Васиссуалий' LIMIT 10
Limit (cost=0.57..39.21 rows=10 width=110)
-> Index Scan using table_name_surname on table (cost=0.57..55887.03 rows=14463 width=110)
Index Cond: ((name)::text = 'Васиссуалий'::text)
EXPLAIN SELECT * FROM table WHERE name='Васиссуалий' ORDER BY id DESC LIMIT 10
Limit (cost=0.57..9487.58 rows=10 width=110)
-> Index Scan Backward using table_pkey on table (cost=0.57..13722019.11 rows=14464 width=110)
Filter: ((name)::text = 'Васиссуалий'::text)
ИМ
кстати id не гарантирует "последний"
СА
"I'm down with Bill Gates, I call him Money for short
I phone him up at home and I make him do my tech support"
I phone him up at home and I make him do my tech support"
СА
Не думаю, что это важно для моих целей, но почему, если там autoincrement? Или в смысле если было две вставки очень близко, то порядок, в котором они в БД попадут, не гарантирован? Да и хрен с ним.
ИМ
да просто был баг проэто) на место удаленных записей можно новые вставлять)