Comments 4
Весьма странная табличка:

1. Смысл в записях вида N/2 хоть и есть, но весьма небольшой — всё равно это лишь ассимптотические оценки, причём с неизвестной константой перед ними.
2. Догадаться о том, что скрывается под названиями струтур данных и операций иногда можно только по временной оценке :-) Но что такое выбор я так и не понял.
3. Ошибки: вместо NlnN должно быть lnN, но одним этим исправлением, боюсь, не отделаться.
4. Бинарный поиск и хэширование структурами данных не являются.
1) Суть записей N/2 в том, что они отражают не оптимальный или худший случай, а средний.
2) Не хочу обижать, но для тех, кто более-менее знаком со струтурами данных, используемых в обработке – эти названия должны быть знакомы. Выбор – извлечение элемента по ключу.
3) Верно – поправил.
4) Дерево бинарного поиска (BST) строится по довольно чётким и давно определённым правилам. По хэширование согласен, но написать хотел всё же про структуры.
1. Я-то как раз понимаю, что имеется в виду под N/2. А вот будет ли очевидна для тех, кому эта таблица может пригодиться, какая связь между «поиск за N», «поиск за N/2» и «вставка за N» и почему все три этих времени различаются? И почему тогда не учтена аналогичная поправка к логрифмам? Потому что посчитать сложнее?
2. Тогда чем поиск отличается от выбора? Вообще, обычно в таких таблицах рассматривается операция удаления.
3. Плохо поправили, не везде. Число ошибок всё равно превышает все разумные пределы. Откуда, например, логарифмы в хешировании и неупорядоченных массивах-списках?
4. Внимательно вглядитесь в вашу же таблицу — я говорил именно про «бинарный поиск», а не про BST.
Вы к табличке еще 2 страничный мануал пояснения должны выложить, что бы вас поняли верно.
У меня вот сразу возникли вопросы:
1-Поиск- это поиск полным перебором имеется ввиду? Но на больших массивах упорядоченных прямым перебором ищут разве что студенты 1 курса. Там бинарный должен быть. Указали бы, что ограничения там на применения алгоритмов. Вспомните, как аккуратно по хирургически люди читающие лекции по алгоритмам ставят постановки.

2-бинарный поиск- что вы вообще имели ввиду под этой формулировкой! На какой структуре данных вы им ищите то? Тк в 1 колонке вроде как структуры данных, а Вы указали алгоритм поиска, а не структуру данных.
и т.д.
Only those users with full accounts are able to leave comments. Log in, please.