Гарвардский университет предлагает курс компьютерных наук, который также бесплатно доступен онлайн, под названием CS50: Introduction to Computer Science. Лекции может посмотреть любой желающий, и я решил не только смотреть лекции, но и писать и делиться конспектами лекций.
Это мои конспекты к лекции 3, посвященной алгоритмам поиска, алгоритмам сортировки, обозначениям временной сложности, структурам данных и рекурсии.
Первая часть этой серии — конспект лекций 0:
Алгоритмы поиска
Эта лекция посвящена алгоритмам, представляющим собой пошаговые инструкции по переходу от ввода к выводу, и их эффективности.
Эффективность алгоритмов изучается путем сравнения того, как увеличивается время выполнения алгоритма по мере увеличения размера входных данных.
Чтобы найти элемент в массиве, вы можете использовать несколько алгоритмов, эти алгоритмы называются алгоритмы поиска.
Линейный поиск
Одним из алгоритмов поиска элемента в массиве является линейный поиск, вот его псевдокод:
for item in array (left to right)
if item is the item you are looking for
return true
return false
Вы возвращаете false только после того, как изучите каждый элемент и не найдете искомый элемент. Обратите внимание, что в обычном коде после возврата выполнение функции останавливается.
Пример линейного поиска при поиске 50 в массиве [20, 500, 10, 5, 100, 1, 50]:
- элемент с индексом 0 равен 20, возврата нет
- элемент с индексом 1 равен 500, возврат невозможен
- элемент в индексе 2 равен 10, возврат невозможен
- элемент с индексом 3 равен 5, возврата нет
- элемент с индексом 4 равен 100, возврата нет
- элемент в индексе 5 равен 1, возврата нет
- элемент с индексом 6 равен 50, вернуть true
Бинарный поиск
Когда массив отсортирован, вы также можете применить алгоритм бинарного поиска, вот его псевдокод:
if array is empty
return false
else if item you are looking for is in the middle
return true
else if item you are looking for is < the middle item
apply binary search on left half
else if item you are looking for is > the middle item
apply binary search on right half
Пример бинарного поиска при поиске 50 в отсортированном массиве [1, 5, 10, 20, 50, 100, 500]:
- Средний элемент [1, 5, 10, 20, 50, 100, 500] равен 20, 50 > 20, поэтому мы применяем бинарный поиск к правой половине.
- Средний элемент [50, 100, 500] равен 100, 50 ‹ 100, поэтому мы применяем бинарный поиск к левой половине.
- Средний элемент [50] равен 50, поэтому верните true
Продолжительность
Время выполнения алгоритма — это время, необходимое для выполнения алгоритма.
Время работы можно выразить несколькими обозначениями. Это обозначения для получения общего представления о том, насколько быстр алгоритм. Например, оно не выражается в точном количестве секунд, поскольку точное время также во многом зависит от таких вещей, как аппаратное обеспечение компьютера.
Время выполнения относится к размеру входных данных. Размер ввода отмечается с помощью n.
Обозначения ориентированы на самый быстрорастущий термин, так как они наиболее актуальны, когда размер входных данных становится действительно большим. Давайте рассмотрим пример лекции 0, где страница пропускается на каждом этапе при просмотре телефонной книги в поисках имени. Если бы мы случайно пропустили искомое имя, нам пришлось бы сделать еще один шаг (вернуться на страницу назад). Поскольку n является количеством страниц, количество шагов алгоритма можно записать как n/2 + 1. Но при сравнении времени работы алгоритмов нас не интересуют меньшие члены, поэтому вместо них мы используем n/2.
И на самом деле, вместо использования n/2 мы просто использовали бы n. Это более общее обозначение скорости алгоритма.
Вот несколько формул, которые используются при сравнении алгоритмов, упорядоченных от медленного к быстрому:
- n² (квадратичное)
- n журнал n
- п (линейный)
- войти n (логарифмический)
- 1 (постоянный)
Обозначение большого O
Обозначение Big O относится к верхней границе (наихудший сценарий). O(n) называется «большой O из n». Можно сказать, что алгоритм линейного поиска имеет порядок n шагов.
Линейный поиск занимает порядка n шагов в худшем случае. Это отмечено с помощью O(n).
Двоичный поиск в худшем случае выполняется порядка log n шагов. Это отмечено с помощью O(log n).
Вот короткая статья, которую я написал о временной сложности и нотации Big O, где вы можете узнать больше об этих темах:
Обозначение Ом
Обозначение Ω (Омега) соответствует нижней границе (в лучшем случае). В этой нотации также используется входной размер n.
Линейный поиск занимает всего 1 шаг в лучшем случае, когда искомый элемент находится в индексе 0 массива. Это обозначается как Ω(1) (омега 1).
Двоичный поиск также занимает всего 1 шаг в лучшем случае, когда искомый элемент находится в середине массива. Это снова обозначается как Ω(1).
Θ Обозначение
Когда алгоритм имеет ту же нотацию Big O, что и нотация Ω, это отмечается другим символом, а именно Θ (тета).
Например, когда вы считаете людей в группе или элементы в списке. Если есть n элементов, вам потребуется n шагов, чтобы подсчитать их как в лучшем, так и в худшем случае. Это можно обозначить как Θ(n).
Линейный поиск в C
Чтобы инициализировать массив с несколькими элементами одновременно, мы можем использовать этот синтаксис:
int numbers[] = {20, 500, 10, 5, 100, 1, 50};
Это создает массив с целочисленными значениями с именем numbers и заполняет его 7 значениями: 20, 500, 10, 5, 100, 1, 50.
Эта программа на C использует алгоритм линейного поиска в массиве целых чисел:
#include <cs50.h>
#include <stdio.h>
int main(void)
{
int numbers[] = {20, 500, 10, 5, 100, 1, 50};
int n = get_int("Number: ");
for (int i = 0; i < 7; i++)
{
if (numbers[i] == n)
{
printf("Found\n");
return 0;
}
}
printf("Not found\n");
return 1;
}
Чтобы выполнить линейный поиск в массиве строк, мы должны использовать функцию библиотеки строк strcmp (сравнение строк). Это так, потому что вы не можете использовать оператор ==, чтобы проверить, равны ли две строки друг другу. Но эту проверку можно выполнить с помощью функции strcmp, которая в этом случае возвращает 0. Вот полный пример кода:
#include <cs50.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
string strings[] = {"battleship", "boot", "cannon", "iron", "thimble", "tophat"};
string s = get_string("String: ");
for (int i = 0; i < 6; i++)
{
if (strcmp(strings[i], s) == 0)
{
printf("Found\n");
return 0;
}
}
printf("Not found\n");
return 1;
}
Если вы создаете 2 массива для хранения 2 функций нескольких объектов, вы можете поместить значения в том же порядке, чтобы функции первого объекта сохранялись в индексе 0 обоих массивов. И особенности второй сущности по индексу 1 и так далее.
Например, если номер телефона Картера — +1–234–567–8901, а номер телефона Дэвида — +1–345–679–9012, вы можете создать 2 таких массива:
string names[] = {"Carter", "David"};
string numbers[] = {"+1-234-567-8901", "+1-345-679-9012"};
В этом случае вы можете реализовать линейный поиск следующим образом:
#include <cs50.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
string names[] = {"Carter", "David"};
string numbers[] = {"+1-234-567-8901", "+1-345-679-9012"};
string name = get_string("Name: ");
for (int i = 0; i < 2; i++)
{
if (strcmp(names[i], name) == 0)
{
printf("Found %s\n", numbers[i]);
return 0;
}
}
printf("Not found\n");
return 1;
}
Но этот метод подвержен ошибкам при добавлении или обновлении значений в массиве.
Вот почему вы можете рассмотреть возможность использования пользовательских структур данных.
Структуры данных в C
В C вы можете реализовать свои собственные структуры данных или типы данных.
Вы можете определить тип данных с именем person и присвоить ему такие атрибуты, как строка для name и строка для number следующим образом:
typedef struct
{
string name;
string number;
}
person;
Затем вы можете создать массив людей с именем people, в котором хранятся 2 человека следующим образом:
person people[2];
Этот синтаксис идентичен созданию массива целых чисел, за исключением того, что теперь мы указываем, что хотим использовать тип данных person вместо int.
Затем мы можем заполнить массив, используя квадратные скобки для указания индекса и точку после этого, чтобы указать, какому атрибуту мы хотим присвоить значение:
people[0].name = "Carter"; people[0].number ="+1-234-567-8901"; people[1].name = "David"; people[1].number = "+1-345-679-9012";
Затем имя и номер человека можно получить с помощью следующего:
people[i].name; people[i].number;
С этими изменениями та же программа, что и раньше, теперь выглядит так, в ней больше строк, но она более управляема, поскольку функции людей инкапсулированы в массив людей:
#include <cs50.h>
#include <stdio.h>
#include <string.h>
typedef struct
{
string name;
string number;
}
person;
int main(void)
{
person people[2];
people[0].name = "Carter";
people[0].number ="+1-234-567-8901";
people[1].name = "David";
people[1].number = "+1-345-679-9012";
string name = get_string("Name: ");
for (int i = 0; i < 2; i++)
{
if (strcmp(people[i].name, name) == 0)
{
printf("Found %s\n", people[i].number);
return 0;
}
}
printf("Not found\n");
return 1;
}
Рекурсия
Рекурсия относится к способности функции вызывать саму себя.
Возьмите этот пример псевдокода бинарного поиска:
1 if array is empty 2 return false 3 else if item you are looking for is in the middle 4 return true 5 else if item you are looking for is < the middle item 6 apply binary search on left half 7 else if item you are looking for is > the middle item 8 apply binary search on right half
в строке 6 и 8 это вызовы для повторения кода.
Важным фактором этого примера кода и рекурсии в целом является то, что когда функция вызывается рекурсивно, размер входных данных становится все меньше и меньше. И в конце концов достигается базовый случай, когда функция не вызывает сама себя. В примере строки 1–2 и 3–4 представляют собой два базовых случая, в которых не выполняются рекурсивные вызовы.
Наличие по крайней мере 1 базового случая и уменьшение размера ввода до достижения базового случая делает так, что рекурсивная функция не вызывает себя бесконечно много раз.
Пример рекурсии в C
Это пример печати следующего вывода с использованием рекурсии.
# ## ### ####
Код для этого основан на фактах:
- пирамиду высотой 4 можно создать, создав пирамиду высотой 3 и линию длиной 4
- пирамиду высотой 3 можно создать, создав пирамиду высотой 2 и линию длиной 3
- пирамиду высотой 2 можно создать, создав пирамиду высотой 1 и линию длиной 2
- пирамида высотой 1 — это всего лишь #
#include <cs50.h>
#include <stdio.h>
#include <string.h>
void draw(int n);
int main(void)
{
int height = get_int("Height: ");
draw(height);
}
void draw(int n)
{
if (n == 1){
printf("#\n");
return;
}
draw(n-1);
for (int i = 0; i < n; i++)
{
printf("#");
}
printf("\n");
}
В функции draw:
Это базовый вариант:
if (n == 1){
printf("#\n");
return;
}
Это гарантирует, что код не будет вызывать себя вечно. В конце концов условие n == 1 должно быть достигнуто, и оператор return сделает так, что никакой другой вызов функции не будет достигнут.
Это рекурсивный вызов функции:
draw(n-1);
Поскольку мы используем n-1, выполнение новой функции будет основано на вводе, более близком к базовому случаю, так что в конечном итоге базовый случай будет достигнут.
После вызова рекурсивной функции мы печатаем строку # под пирамидой, которая будет нарисована рекурсивной функцией.
При прохождении рекурсивной функции. выполнение кода просто следует обычному порядку сверху вниз. Но когда вызывается функция, эта функция сначала выполняется до завершения остальной части исходного вызова функции. Я попытался проиллюстрировать это на следующем изображении:
Выполнение сначала идет все глубже и глубже, делая рекурсивные вызовы (шаги 1, 2 и 3). Затем на шаге 4 достигается базовый случай, который печатает # и возвращает. На шагах 5, 6 и 7 предыдущие вызванные функции завершаются, выполнение начинается после рекурсивного вызова функции.
Алгоритмы сортировки
Алгоритм сортировки — это алгоритм, который принимает несортированный массив в качестве входных данных и возвращает отсортированный массив. Например, если на входе [7, 2, 5, 4, 1, 6, 0, 3], на выходе будет [0, 1, 2, 3, 4, 5, 6, 7]. В некоторых случаях полезно иметь отсортированный массив, например, он позволяет использовать алгоритм бинарного поиска для эффективного поиска значения в массиве.
Подборка короткая
Одним из алгоритмов сортировки является сортировка выбором, он работает следующим образом для нашего примера ввода [7, 2, 5, 4, 1, 6, 0, 3]:
- Перейдите от
7к3, чтобы найти наименьшее значение. Замените наименьшее значение (0) на7. Новый массив[0, 2, 5, 4, 1, 6, 7, 3]. - Перейдите от
2к3, чтобы найти наименьшее значение. Замените наименьшее значение (1) на2. Новый массив[0, 1, 5, 4, 2, 6, 7, 3]. - Перейдите от
5к3, чтобы найти наименьшее значение. Замените наименьшее значение (2) на5. Новый массив[0, 1, 2, 4, 5, 6, 7, 3]. - Перейдите от
4к3, чтобы найти наименьшее значение. Замените наименьшее значение (3) на4. Новый массив[0, 1, 2, 3, 5, 6, 7, 4]. - Перейдите от
5к4, чтобы найти наименьшее значение. Замените наименьшее значение (4) на5. Новый массив[0, 1, 2, 3, 4, 6, 7, 5]. - Перейдите от
6к5, чтобы найти наименьшее значение. Замените наименьшее значение (5) на6. Новый массив[0, 1, 2, 3, 4, 5, 7, 6]. - Перейдите от
7к6, чтобы найти наименьшее значение. Замените наименьшее значение (6) на7. Новый массив[0, 1, 2, 3, 4, 5, 6, 7].
Таким образом, на каждой итерации выбирается наименьшее значение и помещается в начало массива. И на каждой итерации мы начинаем перебирать значения, начиная со значения, расположенного дальше вправо. Вот псевдокод:
for i from 0 to n-1
find smallest number between numbers[i] and numbers[n-1]
swap smallest number with numbers[i]
Для нашего примера с размером входных данных 8 мы сделали 7 сравнений, чтобы найти наименьшее значение в первой итерации, 6 сравнений во второй, 5 в третьей и так далее.
С точки зрения размера входных данных n это может быть записано как:(n-1) + (n-2) + (n-3) + … + 1, что можно переписать как n²/2 - n/2. Наиболее доминирующим термином является n². Так происходит и в лучшем, и в худшем случае, поэтому сортировка выбором имеет O(n²),Ω(n²) и, следовательно, Θ(n²).
Пузырьковая сортировка
Другим алгоритмом сортировки является пузырьковая сортировка, при которой самые высокие значения «пузырьком поднимаются вверх». Начав с начала массива и сравнивая 2 значения за раз и меняя их местами при необходимости, массив сортируется.
Это работает так для нашего примера ввода [7, 2, 5, 4, 1, 6, 0, 3]:
- Поменять местами
7и2, поменять местами7и5, поменять местами7и4, поменять местами7и1, поменять местами7и6, поменять местами7и0, поменять местами7и3, стоп.
Новый массив[2, 5, 4, 1, 6, 0, 3, 7]. - Оставьте
2и5, поменяйте местами5и4, поменяйте местами5и1, оставьте5и6, поменяйте местами6и0, поменяйте местами6и3, стоп.
Новый массив[2, 4, 1, 5, 0, 3, 6, 7]. - Оставьте
2и4, поменяйте местами4и1, оставьте4и5, поменяйте местами5и0, поменяйте местами5и3, стоп.
Новый массив[2, 1, 4, 0, 3, 5, 6, 7]. - Поменяйте местами
2и1, оставьте2и4, поменяйте местами4и0, поменяйте местами4и3, стоп.
Новый массив[1, 2, 0, 3, 4, 5, 6, 7]. - Оставьте
1и2, поменяйте местами2и0, оставьте2и3, остановитесь.
Новый массив[1, 0, 2, 3, 4, 5, 6, 7]. - Поменять местами
1и0, оставить1и2, остановиться.
Новый массив[0, 1, 2, 3, 4, 5, 6, 7]. - Оставьте
0и1, остановитесь.
Новый массив[0, 1, 2, 3, 4, 5, 6, 7].
Псевдокод:
repeat n-1 times
for i from 0 to n-2
if numbers[i] and numbers[i+1] out of order
swap them
Это означает, что псевдокод делает n-1 действие n-1 раз. Это можно отметить как (n-1) * (n-1), то есть (n² - 2n + 1). Наиболее доминирующим термином является n². Так происходит и в лучшем, и в худшем случае, поэтому пузырьковая сортировка также имеет O(n²),Ω(n²) и, следовательно, Θ(n²).
Но если мы видим, что при проходе по значениям обмен не производится, мы можем выйти раньше, так как это означает, что массив уже отсортирован. Это будет новый псевдокод:
repeat n-1 times
for i from 0 to n-2
if numbers[i] and numbers[i+1] out of order
swap them
if no swaps
quit
Это изменит время, необходимое для лучшего сценария, когда массив уже отсортирован, на Ω(n). Θ(n²) больше не будет применяться.
Сортировка слиянием
Сортировка слиянием — это алгоритм сортировки, использующий рекурсию. Он также использует меньше шагов для сортировки массива и быстрее, чем сортировка выбором и пузырьковая сортировка.
Псевдокод такой:
if only 1 number
quit
else
sort left half of numbers
sort left half of numbers
merge sorted halves
Сортировка половинок выполняется рекурсивно до тех пор, пока половинка не будет иметь только 1 номер, что будет базовым случаем. После того, как половинки отсортированы, их можно объединить, повторив этот процесс:
- сравнить первое число обоих массивов
- возьми самый маленький
Например, вот как объединить отсортированные половины [2, 4, 5, 7] и [0, 1, 3, 6]:
- Сравните 2 из [2, 4, 5, 7] с 0 из [0, 1, 3, 6], возьмите 0. | [0]
- Сравните 2 из [2, 4, 5, 7] с 1 из [1, 3, 6], возьмите 1. | [0, 1]
- Сравните 2 из [2, 4, 5, 7] с 3 из [3, 6], возьмите 2. | [0, 1, 2]
- Сравните 4 из [4, 5, 7] с 3 из [3, 6], возьмите 3. | [0, 1, 2, 3]
- Сравните 4 из [4, 5, 7] с 6 из [6], возьмите 4. | [0, 1, 2, 3, 4]
- Сравните 5 из [5, 7] с 6 из [6], возьмите 5. | [0, 1, 2, 3, 4, 5]
- Сравните 7 из [7] с 6 из [6], возьмите 6. | [0, 1, 2, 3, 4, 5, 6]
- Осталось всего 7, бери 7. | [0, 1, 2, 3, 4, 5, 6, 7]
В качестве примера приведено выполнение полного алгоритма сортировки слиянием для сортировки: [7, 2, 5, 4, 1, 6, 0, 3]
- Отсортируйте левую половину [7, 2, 5, 4, 1, 6, 0, 3] = [7, 2, 5, 4].
- Отсортируйте левую половину [7, 2, 5, 4] = [7, 2].
- Отсортируйте левую половину [7, 2] = [7], это всего лишь одно число, так что это делается.
- Отсортируйте правую половину [7, 2] = [2], это всего лишь одно число, так что это делается.
- Объедините левую половину и правую половину [7, 2] = [7] и [2], объединенные [2, 7].
- Отсортируйте правую половину [7, 2, 5, 4] = [5, 4].
- Отсортируйте левую половину [5, 4] = [5], это всего лишь одно число, так что это делается.
- Отсортируйте правую половину [5, 4] = [4], это всего лишь одно число, так что это делается.
- Объедините левую половину и правую половину [5, 4] = [5] и [4] объединены [4, 5].
- Объедините левую половину и правую половину [7, 2, 5, 4] = [2, 7] и [4, 5], объединенные [2, 4, 5, 7].
- Отсортируйте правую половину [7, 2, 5, 4, 1, 6, 0, 3] = [1, 6, 0, 3].
- Отсортируйте левую половину [1, 6, 0, 3] = [1, 6].
- Отсортируйте левую половину [1, 6] = [1], это всего лишь одно число, так что это делается.
- Отсортируйте правую половину [1, 6] = [6], это всего лишь одно число, так что это делается.
- Объедините левую половину и правую половину [1, 6] = [1] и [6], объединенные [1, 6].
- Отсортируйте правую половину [1, 6, 0, 3] = [0, 3].
- Отсортируйте левую половину [0, 3] = [0], это всего лишь одно число, так что это делается.
- Отсортируйте правую половину [0, 3] = [3], это всего лишь одно число, так что это делается.
- Объединить левую половину и правую половину [0, 3] = [0] и [3] объединить [0, 3].
- Объедините левую половину и правую половину [1, 6, 0, 3] = [1, 6] & [0, 3] объединены [0, 1, 3, 6].
- Объедините левую половину и правую половину [7, 2, 5, 4, 1, 6, 0, 3] = [2, 4, 5, 7] & [0, 1, 3, 6] объединены [0, 1 , 2, 3, 4, 5, 6, 7].
Для входного размера 8 алгоритму сортировки слиянием требуется 3 итерации, чтобы разделить их на массивы из 1 (базовый случай). Основание журнала 2 из 8 равно 3, и, в более общем случае, массив длины n требует log n шагов для разделения на массивы из 1. На каждой итерации требуется n шагов, чтобы объединить их вместе. Поэтому наихудший и наилучший сценарии можно отметить с помощью: O(n log n) и Ω(n log n) и, следовательно, Θ (n log n).
Компромиссы
Как мы видели, сортировка слиянием работает быстрее, чем сортировка выбором и пузырьковая сортировка, но для выполнения алгоритма сортировки слиянием требуется немного больше памяти. Это пример компромисса между меньшим временем и большим пространством или большим временем и меньшим пространством.
Другой компромисс, который вы можете рассмотреть, заключается в том, стоит ли тратить дополнительное время на первую сортировку массива, чтобы иметь возможность искать быстрее с помощью двоичного поиска. Или просто выполните более медленный линейный поиск в несортированном массиве. Решение может зависеть от количества поисков, которые вы будете выполнять в отсортированном массиве.
Спасибо за чтение!
Надеюсь мой пост был полезен.
Если вам понравилось, подписывайтесь на мою страницу, чтобы узнать другие конспекты лекций по CS50 и узнать больше о программировании, это мне очень поможет:
Следующая лекция посвящена Памяти.
