Прикладные структуры данных и алгоритмы. Прокачиваем навыки
Қосымшада ыңғайлырақҚосымшаны жүктеуге арналған QR
goole playappstore
RuStore · Samsung Galaxy Store
Huawei AppGallery · Xiaomi GetApps

автордың кітабынан сөз тіркестері  Прикладные структуры данных и алгоритмы. Прокачиваем навыки
Джей Венгроу

РузаNOVA
РузаNOVAдәйексөз келтірді6 ай бұрын
при измерении скорости выполнения операции мы учитываем не количество времени, а число шагов, которое для этого требуется.
1 Ұнайды
Комментарий жазу
Alexandra L.
Alexandra L.дәйексөз келтірді14 сағат бұрын
На эффективность хеш-таблицы влияют три фактора: • количество хранящихся данных; • число доступных ячеек; • используемая хеш-функция.
Комментарий жазу
Даниэль
Даниэльдәйексөз келтірді2 апта бұрын
Но в случае с упорядоченным массивом мы можем остановить поиск раньше, даже если искомого значения в массиве нет. Допустим, мы ищем число 22 в упорядоченном массиве [3, 17, 75, 80, 202]. Мы можем остановить поиск, как только дойдем до 75, поскольку 22 никак не может быть справа от него.
Комментарий жазу
Даниэль
Даниэльдәйексөз келтірді2 апта бұрын
Интересно, что это количество шагов остается одинаковым вне зависимости от того, в какую именно позицию массива помещается новое значение. При вставке значения в начало мы выполняем меньше сравнений и больше сдвигов, а ближе к концу — больше сравнений, но меньше сдвигов. Меньше всего шагов нужно для вставки нового значения в самый конец, так как эта операция не подразумевает никаких сдвигов. В этом случае мы выполняем N шагов для сравнения нового значения со всеми существующими и один для самой вставки, что в общей сложности дает N + 1 шагов.
Комментарий жазу
Даниэль
Даниэльдәйексөз келтірді2 апта бұрын
В худшем случае при вставке значения в начало множества компьютеру придется проверить N ячеек, чтобы убедиться, что множество еще не содержит вставляемого значения, выполнить N шагов, чтобы сдвинуть все значения вправо, и еще один для вставки нового значения. Итого: 2N + 1 шагов
Комментарий жазу
Даниэль
Даниэльдәйексөз келтірді2 апта бұрын
Иначе говоря, вставка значения в конец множества из N элементов может потребовать до N + 1 шагов: N шагов для поиска, чтобы убедиться в отсутствии вставляемого значения, и один для фактической вставки.
Комментарий жазу
Даниэль
Даниэльдәйексөз келтірді2 апта бұрын
Итак, в случае с множеством каждая операция вставки требует предварительного выполнения поиска.
Комментарий жазу
Даниэль
Даниэльдәйексөз келтірді2 апта бұрын
Чтение из множества выполняется точно так же, как и из массива — чтобы выяснить значение в позиции с определенным индексом, компьютеру нужен всего один шаг.
Комментарий жазу
Даниэль
Даниэльдәйексөз келтірді2 апта бұрын
Следовательно, операция удаления значения из массива, состоящего из N элементов, потребует максимум N шагов.
Комментарий жазу
Даниэль
Даниэльдәйексөз келтірді2 апта бұрын
Проще говоря, в худшем случае вставка значения в массив из N элементов может потребовать N + 1 шагов, ведь перед вставкой нового значения нам нужно переместить все N элементов.
Комментарий жазу