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

Кітап туралы Пікірлер8 Дәйексөздер251 Қазір оқып жатыр4.2K Сөрелерде

при измерении скорости выполнения операции мы учитываем не количество времени, а число шагов, которое для этого требуется.

1 Ұнайды

Комментарий жазу

Алексей Стакундәйексөз келтірді1 күн бұрын

Алгоритм со сложностью O(N 2) считается относительно неэффективным, так как по мере роста объема данных число шагов увеличивается очень резко. Взгляните на следующий график, где O(N 2) сравнивается с более быстрым алгоритмом O(N):

Обратите внимание на то, как резко растет кривая, отражающая количество шагов алгоритма O(N 2), по сравнению с простой диагональной линией O(N).

Комментарий жазу

Алексей Стакундәйексөз келтірді1 күн бұрын

Пузырьковая сортировка, или сортировка пузырьком, — это простейший алгоритм сортировки, который выполняет следующие шаги.

1. Указывает на два соседних значения в массиве, начиная с первых двух. Сравнивает первый элемент со вторым:

2. Если эти два элемента расположены не по порядку (например, левое значение больше правого), меняет их местами (если они в правильном порядке, то ничего не делает):

3. Сдвигает указатели на одну ячейку вправо:

4. Повторяет шаги с 1 по 3, пока не достигнет конца массива. Так выглядит первый проход по массиву — последовательное указание на все содержащиеся в нем значения.

5. Затем указатели возвращаются к первым двум значениям и выполняется еще один проход по массиву с повторением шагов с 1 по 4. Эти проходы повторяются, пока не выяснится, что перестановки значений больше не нужны. Это говорит о том, что наш массив полностью отсортирован и задача выполнена.

Комментарий жазу

Алексей Стакундәйексөз келтірді2 апта бұрын

Цель в этом примере немного отличается от тех, что были ранее. Раньше нас интересовало количество шагов алгоритма при наличии в массиве N элементов данных. Здесь мы имеем дело не с массивом, а с числом, которое передаем функции, и от величины этого числа зависит то, сколько раз будет выполняться цикл.

Ключевой вопрос в этом случае будет следующим: «Сколько шагов будет выполнять алгоритм при передаче числа N?»

Если мы передадим функции is_prime число 7, то цикл for будет выполняться примерно семь раз (технически он выполняется пять раз: диапазон чисел, на которые производится деление, начинается с 2 и заканчивается перед заданным числом). В случае с числом 101 цикл выполняется примерно 101 раз. Поскольку количество шагов алгоритма увеличивается на один, когда повышается на единицу величина переданного функции числа, мы имеем дело с классическим примером алгоритма со сложностью O(N).

Комментарий жазу

Алексей Стакундәйексөз келтірді2 апта бұрын

В мире информатики под выражением O(log N) подразумевается выражение O(log2 N).

Комментарий жазу

Алексей Стакундәйексөз келтірді2 апта бұрын

Запишем рассмотренные типы алгоритмов в порядке убывания эффективности:

O(1);

O(log N);

O(N).

Теперь посмотрим, как это выражается графически:

Обратите внимание, что кривая O(log N) растет очень медленно. Это делает алгоритм менее эффективным, чем O(1), но более эффективным, чем O(N).

Комментарий жазу

Алексей Стакундәйексөз келтірді2 апта бұрын

O(log N) описывает алгоритм, число шагов в котором увеличивается на единицу при каждом удвоении объема данных.

Комментарий жазу

Алексей Стакундәйексөз келтірді2 апта бұрын

сложность алгоритма двоичного поиска находится где-то между O(1) и O(N). Так какова же она?

Временная сложность двоичного поиска выражается с помощью О-нотации так: O(log N).

Комментарий жазу

Алексей Стакундәйексөз келтірді2 апта бұрын

Если бы мы захотели максимально полно описать эффективность этого алгоритма, то сказали бы, что сложность линейного поиска равна O(1) в лучшем случае и O(N) — в худшем.

Комментарий жазу

Алексей Стакундәйексөз келтірді2 апта бұрын

Поскольку всегда есть некая точка перелома, по достижении которой алгоритм O(N) начинает выполнять больше шагов, вплоть до бесконечности, в целом он считается менее эффективным, чем O(1), вне зависимости от того, сколько шагов выполняет последний.

Комментарий жазу

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

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