Дополнительные материалы CS50 (Week 3, лекции 7 и 8): асимптотическая нотация, алгоритмы сортировки и поиска

Лекции Гарвардского курса по основам программирования CS50 Задания CS50, week 3, часть 1 Задания CS50, week 3, часть 2

Асимптотическая нотация

Измерить скорость алгоритма реальным временем — секундами и минутами — непросто. Одна программа может работать медленнее другой не из-за собственной неэффективности, а по причине медлительности операционной системы, несовместимости с оборудованием, занятости памяти компьютера другими процессами… Чтобы измерять эффективность алгоритмов придумали универсальные концепции вне зависимости от среды, в которой запущена программа. Измерение ассимптотической сложности задачи измеряется с помощью нотации О-большого. Пусть f(x) и g(x) — функции, определенные в некой окрестности x0, причем g там не обращается в 0. Тогда f является «O» большим от g при (x -> x0), если существует константа C>0, что для всех x из некоторой окрестности точки x0 имеет место неравенство |f(x)| <= C |g(x)| Чуть менее строго: f является «O» большим от g, если существует константа C>0, что для всех x > x0 f(x) <= C*g(x) Не бойтесь формального определения! По сути, оно определяет асимптотическое возрастание времени работы программы, когда количество ваших данных на входе растет в сторону бесконечности. Например, вы сравниваете сортировку массива из 1000 элементов и 10 элементов и нужно понять, как возрастёт при этом время работы программы. Или нужно подсчитать длину строки символов путем посимвольного прохода и прибавлением 1 за каждый символ: c - 1 a - 2 t - 3 Его асимптотическая скорость = О(n), где n — количество букв в слове. Если считать по такому принципу, время, необходимое для подсчета всей строки, пропорционально количеству символов. Подсчет количества символов в строке из 20 символов занимает вдвое больше времени, нежели при подсчете количества символов в десятисимвольной строке. Представьте, что в переменной length вы сохранили значение, равное количеству символов в строке. Например, length = 1000. Чтобы получить длину строки, нужен только доступ к этой переменной, на саму строку можно даже не смотреть. И как бы мы ни меняли длину, мы всегда можем обратиться к этой переменной. В таком случае асимптотическая скорость = O(1). От изменения входных данных скорость работы в такой задаче не меняется, поиск завершается за постоянное время. В таком случае программа является асимптотически постоянной. Недостаток: вы тратите память компьютера на хранение дополнительной переменной и дополнительное время для обновления её значения. Если вам кажется, что линейное время — это плохо, смеем заверить: бывает гораздо хуже. Например, O(n²). Такая запись означает, что с ростом n рост времени, нужного для перебора элементов (или другого действия) будет расти всё резче. Но при маленьких n алгоритмы с асимптотической скоростью О(n²) могут работать быстрее, чем алгоритмы с асимптотикой О(n). Но в какой-то момент квадратичная функция обгонит линейную, от этого не уйти. Еще одна асимптотическая сложность — логарифмическое время или O(log n). С ростом n эта функция возрастает очень медленно. О(log n) — время работы классического алгоритма бинарного поиска в отсортированном массиве (помните разорванный телефонный справочник на лекции?). Массив делится надвое, затем выбирается та половина, в которой находится элемент и так, каждый раз уменьшая область поиска вдвое, мы ищем элемент. Что будет, если мы сразу наткнемся на искомое, разделив в первый раз наш массив данных пополам? Для лучшего времени есть термин — Омега-большое или Ω(n). В случае бинарного поиска = Ω(1) (находит за постоянное время независимо от размера массива). Линейный поиск работает за время O(n) и Ω(1), если искомый элемент — самый первый. Еще один символ — тета (Θ(n)). Он используется, когда лучший и худший варианты одинаковы. Это подходит для примера, где мы хранили длину строки в отдельной переменной, поэтому при любой её длине достаточно обратиться к этой переменной. Для этого алгоритма лучший и худший варианты равны соответственно Ω(1) и O(1). Значит, алгоритм работает за время Θ(1).

Линейный поиск

Когда вы открываете веб-браузер, ищете страничку, информацию, друзей в соцсетях, вы совершаете поиск, точно так же, как при попытке найти нужную пару обуви в магазине. Вы наверняка замечали, что упорядоченность сильно влияет на то, как вы ищете. Если у вас все рубашки лежат в шкафу, найти среди них нужную обычно проще, чем среди разбросанных без системы по всей комнате. Линейный поиск — способ последовательного поиска, один за одним. Когда вы пересматриваете результаты поиска в Google сверху вниз, вы используете линейный поиск. Пример. пусть у нас есть список чисел: 2 4 0 5 3 7 8 1 И нам нужно найти 0. Мы его видим сразу, но компьютерная программа так не работает. Она начинает с начала списка и видит число 2. Затем проверяет, 2=0? Это не так, поэтому она продолжает работу и переходит ко второму символу. Там её тоже ждет неудача, и только на третьей позиции алгоритм находит нужное число. Псевдокод линейного поиска: Функция linearSearch получает на вход два аргумента — ключ key и массив array[].Ключ — искомое значение, в предыдущем примере key = 0. Массив — список чисел, которые мы будем просматривать. Если мы ничего не нашли, функция вернет -1 (позицию, которой в массиве нет). Если же линейный поиск найдет нужный элемент, то функция вернет позицию, на которой находится искомый элемент в массиве. В линейном поиске хорошо то, что он будет работать для любого массива, независимо от порядка элементов: мы всё равно пройдём по всему массиву. Это же является и его слабостью. Если вам нужно найти число 198 в массиве из 200 чисел, отсортированных по порядку, цикл for пройдет 198 шагов. Вы, вероятно, уже догадались, какой способ работает лучше для отсортированного массива?

Бинарный поиск и деревья

Представьте, что у вас есть список отсортированных по алфавиту диснеевских героев, и вам нужно найти Микки Мауса. Линейно это было бы долго. А если воспользоваться «методом разрывания справочника пополам», мы попадаем сразу на Jasmine, и можем смело отбросить первую половину списка, понимая, что Mickey там не может быть. По этому же принципу отбрасываем второй столбец. Продолжая такую стратегию, мы найдем Микки буквально за пару шагов. Давайте найдем число 144. Делим список пополам, и попадаем на число 13. Оцениваем, больше или меньше искомое число, чем 13. 13 < 144, так что мы можем игнорировать всё, что находится левее 13 и само это число. Теперь наш список поиска выглядит так: Тут чётное число элементов, поэтому выбираем принцип, по которому выбираем «среднее» (ближе к началу или концу). Допустим, мы избрали стратегию близости к началу. В таком случае, наша «середина» = 55. 55 < 144. Мы снова отбрасываем левую половину списка. К счастью для нас, следующее среднее число и будет 144. Мы нашли 144 в массиве из 13 элементов с помощью бинарного поиска всего за три шага. Линейный поиск в такой же ситуации справился бы аж за 12 шагов. Поскольку этот алгоритм на каждом шаге уменьшает количество элементов в массиве вдвое, он найдет искомое за асимптотическое время О(log n), где n – количество элементов в списке. То есть, в нашем случае асимптотическое время = O(log 13) (это чуть больше трёх). Псевдокод функции бинарного поиска: Функция принимает на вход 4 аргумента: искомое key, массив данных array [], в котором находится искомое, min и max — указатели на максимальное и минимальное число в массиве, на которое мы смотрим на данном шаге алгоритма. Для нашего примера изначально дана такая картинка: Разберем код далее. midpoint — наша середина массива. Она зависит от крайних точек и находится по центру между ними. После того, как мы нашли середину, проверяем, меньше ли она нашего числа key. Если это так, то key также больше, чем любое из чисел левее середины, и мы можем вызвать бинарную функцию снова, только теперь наш min = midpoint + 1. Если окажется, что key < midpoint, мы можем отбросить само это число и все числа, лежащие справа от него. И мы вызываем бинарный поиск по массиву от числа min и вплоть до значения (midpoint – 1). Наконец, третья ветка: если значение в midpoint не больше и не меньше, чем key, ему ничего не остается, как быть искомым числом. Его мы и возвращаем в таком случае и заканчиваем работу программы. Наконец, может статься так, что искомое число и вовсе отсутствует в массиве. Для учёта этого случая делаем такую проверку: И возвращаем (-1), чтобы указать, что мы ничего не нашли. Вы уже знаете, что для бинарного поиска необходимо, чтобы массив был отсортирован. Таким образом, если у нас есть неотсортированный массив, в котором нужно найти некий элемент, у нас есть два варианта действия:

1. Отсортировать список и применить бинарный поиск
2. Сохранять список всегда отсортированным при одновременном добавлении и убирании из него элементов.

Один из способов хранения списков отсортированными считается бинарное дерево поиска. Бинарное (двоичное) дерево поиска — это структура данных, которая отвечает следующим требованиям:

• Оно является деревом (структурой данных, эмулирующей древовидную структуру — имеет корень и другие узлы (листья), связанные «ветками» или ребрами без циклов)
• Каждый узел имеет 0, 1 или 2 потомка
• Оба поддерева — левое и правое — являются двоичными деревьями поиска.
• У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
• У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равно, нежели значение ключа данных самого узла X.

Внимание: корень «программистского» дерева, в отличие от реального, находится сверху. Каждая ячейка называется вершиной, вершины соединены ребрами. Корень дерева — ячейка с номером 13. Левое поддерево вершины 3 выделено цветом на картинке снизу: Наше дерево соответствует всем требованиям к бинарным деревьям. Это значит, что каждое его левое поддерево содержит только значения, которые меньше или равны значению вершины, правое — только значения большие или равные значению вершины. Оба левые и правые поддеревья сами являются бинарными поддеревьями. Способ построения бинарного дерева — не единственный: ниже на картинке вы видите ещё один вариант для того же набора чисел, и их может быть очень много на практике. Такая структура помогает проводить поиск: минимальное значение находим, двигаясь от вершины влево-вниз каждый раз. Если нужно найти максимальное число — идем от вершины вниз и вправо. Нахождение числа, которое не является минимальным или максимальным также весьма простое. Мы спускаемся от корня влево или вправо в зависимости от того, больше или меньше наша вершина искомой. Так, если нам нужно найти число 89 мы проходим вот такой путь: Еще можно выводить числа в порядке сортировки. Например, если нам нужно вывести все числа в порядке возрастания, берем левое поддерево и начиная с самой левой вершины идем наверх. Прибавить что-то в дерево тоже просто. Главное помнить о структуре. Скажем, нам нужно добавить в дерево значение 7. Идем к корню, и проверяем. Число 7 < 13, поэтому идем влево. Там видим 5, и идем вправо, поскольку 7 > 5. Дальше поскольку 7 > 8 и 8 не имеет потомков, мы конструируем ветку от 8 влево и на неё цепляем 7. Также можно удалять вершины из дерева, но это несколько сложнее. Есть три разных сценария для удаления, которые мы должны учесть.

1. Самый простой вариант: нам нужно удалить вершину, у которой нет потомков. Например, число 7, которое мы только что добавили. В таком случае мы просто проходим путь до вершины с этим числом и удаляем его.
2. У вершины есть одна вершина-потомок. В таком случае можно удалить нужную вершину, но её потомка нужно подсоединить к «дедушке», то есть вершине, из которой произрастал её непосредственный предок. Например, из того же дерева нужно удалить число 3. В таком случае, её потомка, единицу, вместе со всем поддеревом присоединяем к 5. Это делается просто, поскольку все вершины, слева от 5, будут меньше чем это число (и меньше, чем удалённая тройка).
3. Самый сложный случай — когда у удаляемой вершины есть два потомка. Теперь первым делом нам нужно найти вершину, в которой спрятано следующее большее значение, нужно поменять их местами, а потом удалить нужную вершину. Обратите внимание: следующая по значению вершина не может иметь двух потомков, тогда её левый потомок будет лучшим кандидатом на следующее значение. Давайте из нашего дерева удалим корневую вершину 13. Сначала ищем самое близкое к 13 число, которое его больше. Это 21. Меняем 21 и 13 местами и удаляем 13.

Есть разные способы строить бинарные деревья, одни хорошие, другие — не очень. Что будет, если мы попробуем построить бинарное дерево из отсортированного списка? Все числа просто будут прибавляться в правую ветку предыдущего. Если мы захотим найти число, у нас не будет другого выхода, как просто идти по цепочке вниз. Это ничуть не лучше, чем линейный поиск. Есть и другие структуры данных, более сложные. Но их мы пока рассматривать не будем. Скажем только, что для решения проблемы с построением дерева из отсортированного списка можно перемешать входные данные случайным образом.

Алгоритмы сортировки

Есть массив чисел. Нужно его отсортировать. Для простоты будем считать, что мы сортируем целые числа в порядке возрастания (от меньшего к большему). Существует несколько известных способов провернуть этот процесс. Плюс, вы всегда можете пофантазировать на тему и придумать модификацию алгоритма.

Сортировка выбором

Основная идея — разбить наш список на две части, отсортированную и неотсортированную. На каждом шаге алгоритма новое число перемещается из неотсортированной части в отсортированную, и так пока все числа не окажутся в отсортированной части.

1. Находим минимальное неотсортированное значение.
2. Меняем местами это значение с первым неотсортированным значением, ставя его таким образом в конец отсортированного массива.
3. Если остались неотсортированные значения, возвращаемся к шагу 1.

На первом шаге все значения являются неотсортированными. Назовем неотсортированную часть — Unsorted, а отсортированную — Sorted (это просто английские слова, и делаем мы это только потому, что Sorted — гораздо короче, чем «Отсортированная часть» и будет лучше смотреться на картинках). Находим минимальное число в неотсортированной части массива (то есть, на этом шаге — во всем массиве). Это число 2. Теперь меняем его с первым среди неотсортированных и ставим его в конец отсортированного массива(на этом шаге — на первое место). На этом шаге это первое число в массиве, то есть 3. Шаг второй. На число 2 мы не смотрим, оно уже в отсортированном подмассиве. Начинаем искать минимальное, начиная со второго элемента, это 5. Убеждаемся, что 3 — минимальное среди неотсортированных, 5 — первое среди неотсортированных. Меняем их местами и прибавляем 3 к отсортированному подмассиву. На третьем шаге мы видим, что в неотсортированном подмассиве самое маленькое число — 4. Меняем его с первым числом среди неотсортированных — 5. На четвертом шаге мы обнаруживаем, что в неотсортированном массиве минимальное число — 5. Меняем его с 6 и прибавляем к отсортированному подмассиву. Когда среди неотсортированных остается только одно число (наибольшее), это значит, что весь массив отсортирован! Вот как выглядит реализация массива в коде. Попробуйте сделать его самостоятельно. В обоих, самом лучшем и самом худшем случаях, чтобы найти минимальный неотсортированный элемент, мы должны сравнить каждый элемент с каждым элементом неотсортированного массива, и делать это мы будем на каждой итерации. Но нам нужно просматривать не весь список, а только неотсортированную часть. Меняет ли это скорость алгоритма? На первом шаге для массива из 5 элементов мы делаем 4 сравнения, на втором — 3, на третьем — 2. Чтобы получить количество сравнений, нам нужно сложить все эти числа. Мы получаем сумму Таким образом, ожидаемая скорость алгоритма в лучшем и худшем случае — Θ(n²). Не самый эффективный алгоритм! Тем не менее, для учебных целей и для небольших массивов данных — вполне применимый.

Пузырьковая сортировка

Алгоритм у пузырьковой сортировки — один из простейших. Идем вдоль всего массива и сравниваем 2 соседних элемента. Если они в неправильном порядке, меняем их местами. При первом проходе в конце окажется («всплывет») самый маленький элемент (если мы сортируем в порядке убывания). Повторять первый шаг, если хотя бы один обмен на предыдущем шаге был совершен. Давайте отсортируем массив. Шаг 1: идем по массиву. Алгоритм начинает работу с первых двух элементов, 8 и 6 и проверяет, находятся ли они в правильном порядке. 8 > 6, поэтому меняем их местами. Далее мы смотрим на второй и третий элементы, теперь это 8 и 4. Из тех же соображений меняем их местами. В третий раз сравниваем 8 и 2. Итого, мы делаем три обмена (8, 6), (8, 4), (8, 2). Значение 8 «всплыло» в конец списка на правильную позицию. Шаг 2: меняем местами (6,4) и (6,2). 6 теперь на предпоследней позиции, и её можно не сравнивать с уже отсортированным «хвостом» списка. Шаг 3: меняем местами 4 и 2. Четверка «всплывает» на свое законное место. Шаг 4: проходимся по массиву, но менять нам уже нечего. Это сигнализирует о том, что массив полностью отсортирован. А это — код алгоритма. Попробуйте реализовать его на Си! Пузырьковая сортировка проходит за время O(n²) в худшем случае (все числа стоят неправильно), поскольку нам нужно сделать n шагов на каждой итерации, которых тоже n. На самом деле, как и в случае с алгоритма сортировки выбором, время будет несколько меньше (n²/2 – n/2), но этим можно пренебречь. В лучшем случае (если все элементы уже стоят на своем месте), мы справимся за n шагов, т.е. Ω(n), поскольку нам нужно будет просто пробежаться по массиву один раз и убедиться, что все элементы стоят на своих местах (т.е. даже n-1 элементов).

Сортировка вставками

Основная идея этого алгоритма — разделение нашего массива на две части, отсортированную и неотсортированную. На каждом шаге алгоритма число переходит от неотсортированной к отсортированной части. Давайте на примере ниже разберем, как работает сортировка вставкой. До того, как мы начали, все элементы считаются неотсортированными. Шаг 1. Возьмем первое неотсортированное значение (3) и вставим его в отсортированный подмассив. На этом шаге весь отсортированный подмассив, его начало и конец и будут этой самой тройкой. Шаг 2. Поскольку 3 > 5, мы вставим 5 в отсортированный подмассив справа от 3. Шаг 3. Теперь работаем над вставкой числа 2 в наш отсортированный массив. Сравниваем 2 со значениями справа налево, чтобы найти правильную позицию. Поскольку 2 < 5 и 2 < 3 и мы дошли до начала отсортированного подмассива. Следовательно, мы должны вставить 2 слева от 3. Для этого подвигаем 3 и 5 вправо, чтобы появилось место для двойки и вставляем её в начало массива. Шаг 4. Нам повезло: 6 > 5, поэтому мы можем вставить это число сразу за числом 5. Шаг 5. 4 < 6 и 4 < 5, но 4 > 3. Следовательно, мы знаем, что 4 нужно вставить справа от 3. Снова, мы вынуждены подвинуть 5 и 6 вправо, чтобы создать лакуну для 4. Готово! Обобщенный алгоритм: Берем каждый неотсортированный элемент n и сравниваем его со значениями в отсортированном подмассиве справа налево, пока не определим подходящую позицию для n (то есть, в тот момент, когда находим первое число, которое меньше, чем n). Затем сдвигаем все отсортированные элементы, которые находятся справа от этого числа вправо, чтобы образовалось место для нашего n, м вставляем его туда, тем самым расширяя отсортированную часть массива. Для каждого неотсортированного элемента n нужно:

2. Определить место в отсортированной части массива, куда нужно вставить n
3. Сдвинуть отсортированные элементы вправо, чтобы сделать лакуну для n
4. Вставить n в образовавшуюся лакуну в отсортированной части массива.

А вот и код! Рекомендуем написать свою версию программы сортировки.

Асимптотическая скорость алгоритма

В самом плохом случае мы сделаем одно сравнение со вторым элементом, два сравнения с третьим и так далее. Таким образом наша скорость равна O(n²). В лучшем случае мы будем работать с уже отсортированным массивом. Отсортированная часть, которую мы строим слева направо без вставок и передвижений элементов займет время Ω(n).

Сортировка слиянием

Этот алгоритм — рекурсивный, он разбивает одну большую задачу сортировки на подзадачи, выполнение которых делают его ближе к решению изначальной большой задачи. Основная идея — разделение неотсортированного массива на две части и сортировка отдельных половинок по рекурсивному принципу. Допустим, у нас есть n элементов для сортировки. Если n < 2, заканчиваем сортировку, иначе — сортируем отдельно левую и правую части массива, и потом их объединяем. Давайте отсортируем массив Делим его на две части, и продолжаем делить, пока не получим подмассивы величиной 1, которые заведомо отсортированы. Два отсортированных подмассива можно объединить за время O(n) с помощью простого алгоритма: удаляем меньшее из чисел в начале каждого подмассива и вставляем его в объединенный массив. Повторяем, пока не закончатся все элементы. Сортировка слиянием требует времени O(nlog n) для всех случаев. Пока мы делим массивы на половины на каждом уровне рекурсии получаем log n. Затем, для слияния подмассивов нужно всего n сравнений. Следовательно, O(nlog n). Лучший и худший варианты для сортировки слиянием — одинаковы, ожидаемое время работы алгоритма = Θ(nlog n). Этот алгоритм — самый эффективный среди рассмотренных.