Программирование на С с нуля

Содержание

Бинарный поиск
- Задача
  - Более эффективный алгоритм поиска - Больше или Меньше
  - ЛОГАРИФМЫ
Время выполнения
O-Большое
Сортировка выбором
Рекурсия
- Базовый случай и рекурсивный случай
- Стек
  - Стек вызовов
  - Стек вызовов с рекурсией
Быстрая сортировка
Хеш-таблицы
Поиск в ширину
Деревья
Сбалансированные деревья
Алгоритм Дейкстры
Жадные алгоритмы
Динамическое программирование
Алгоритм k ближайших соседей
Дополнительные Алгоритмы
Приложения

Бинарный поиск

Бинарный поиск — это алгоритм; на входе он получает уже отсортированный список элементов (позднее я объясню, почему он должен быть отсортирован). Если элемент, который вы ищете, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден. В противном случае бинарный поиск возвращает NULL.

Рассмотрим как работает бинарный поиск. Вот простая игра: я загадал число от 1 до 100, какое?

Задача

Дано сто чисел. Нужно найти Одно конкретное.

Цель

Найти число, использовав как можно меньше попыток.

Анализ и рассуждение

Предположим, вы начнёте перебирать каждый элемент из списка подряд: 1, 2, 3, 4… Для решения задачи таким способом, можно написать цикл прохождения по массиву чисел, и с помощью условия сравнивать введённое вами число(предполагаемый ответ) с текущим числом по индексу элемента.

#include <stdio.h>

int main(void)
{
    int array[100] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
                      21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
                      41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
                      61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
                      81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100};

    printf("\nEnter Number to search: ");
    int user_number;
    scanf("%d", &user_number);
    for (int i = 0; i < sizeof(array) / sizeof(int); i++)
    {
        if (user_number == array[i])
        {
            printf("\nNumber %d finded, %d tries were spent.\n\n", user_number, ++i);
        }
    }
    return 0;
}

Чем больше элементов в списке, тем дольше искать.

Берём первый элемент списка и сравниваем с наши числом. Числа совпали? Если да - задача выполнена. Если нет - переходим к следующему элементу списка, и так пока не найдём искомое число.

С учётом того, какого размера список чисел нам предстоит обработать, просто перебирая одно число за другим, мы рано или поздно нужное число найдём. Это простой алгоритм, и нам нужно сделать максимум 100 попыток, минимум 1-ну попытку.

Если будет использоваться простой список последовательно размещённых в нём чисел от 1 до 100, то чтобы наткнуться на число 50, нам потребуется всего пятьдесят попыток. Если число будет 100 - то сто попыток. А если нужно было найти число 1 - то мы с первой попытки найдём ответ.

Таким образом - чем длиннее список, тем дольше нам искать, особенно если число стоит в конце списка последним. А есть ли более эффективный алгоритм, чтобы найти искомое число быстрее?

Более эффективный алгоритм поиска - Больше или Меньше

Существует другой, более эффективный способ. Начнём с числа-условия 50. Теперь, когда пользователь введёт число, это число нужно проверить на условие Больше или Меньше чем 50. Если введённое пользователем число Меньше 50, алгоритм отреагирует сообщением: "Мало - Недобор". Половина ненужных от сотни попыток отсеяна!

Пользователь вводит число 75(посередине оставшегося диапазона чисел - между 51 и 100). Если введённое пользователем число Больше 50, алгоритм отреагирует сообщением: "Много - Перебор".

С бинарным поиском вы каждый раз загадываете число в середине диапазона и исключаете половину оставшихся чисел.

Теперь число лежит где-то в пределах от 51 до 74 включительно. Пользователь вводит число 63, алгоритм снова реагирует сообщением: "Много - Перебор". Теперь диапазон от 51 до 64 включительно.

Пользователь вводит число 57, алгоритм реагирует сообщением: "Угадал".

Это и есть принцип работы алгоритма Бинарного поиска. Посчитаем сколько шагов потребуется для нахождения числа в массиве из ста чисел в худшем случаи:

Вместо 57 шагов, для числа 57, мы нашли его за 4 шага. Это более чем в 14 раз быстрее, чем последовательный перебор каждого элемента в списке! Почему так быстрее: При Бинарном поиске каждый раз исключается половина чисел. Плюс, к тому, число 57 мы просто на четвёртом шаге угадали. Но в принципе 7 шагов это максимум, которые нам потребуются чтобы гарантированно найти число в массиве из ста элементов.

Алгоритм работает не только с массивом в сто чисел. Бинарный поиск гарантирует, что его алгоритм позволит найти число в массиве любого размера не перебирая каждый его элемент!

Например, у вас есть электронная энциклопедия, в ней 300 000 слов (триста тысяч). Сколько попыток вы потратите, применяя алгоритм Бинарного поиска чтобы найти число 125801?

Понятно, что если перебирать по порядку каждое слово, то будет потрачено 125 801 шагов. А с помощью Бинарного поиска, сколько? Давайте проанализируем.

Вместо 125801 шагов, число мы нашли за 20 шагов. Это более чем в 6290 раз быстрее, чем последовательный перебор каждого элемента в списке! Почему так быстрее: При Бинарном поиске каждый раз исключается половина чисел.

В общем случае для списка из n элементов бинарный поиск выполняется за log₂n шагов, тогда как простой поиск будет выполнен за n шагов.

ЛОГАРИФМЫ

Возможно, вы уже забыли, что такое логарифм, но наверняка помните, что такое возведение в степень. log₁₀100, по сути, означает, сколько раз нужно перемножить 10, чтобы получить 100. Правильный ответ — 2: 10 × 10. Итак, log₁₀100 = 2. Логарифм по смыслу противоположен возведению в степень:
10² = 100 ⟷ log₁₀100 = 2
10³ = 1000 ⟷ log₁₀1000 = 3
2³ = 8 ⟷ log₂8 = 3
2⁴ = 16 ⟷ log₂16 = 4
2⁵ = 32 ⟷ log₂32 = 5
Логарифм — операция, обратная возведению в степень.

Когда здесь упоминается O-большое (далее подробнее), log всегда означает log₂. Когда вы ищете элемент с применением простого поиска, это считается худшим случаем, вам придётся проверить каждый элемент в списке. Итак, для списка из 8-ми чисел понадобится не больше 8-ми проверок. Для бинарного поиска в худшем случае потребуется не более log₂n проверок. Для списка из 8 элементов log₂8 == 3, потому что 2³ == 8. Итак, для списка из 8 чисел вам придётся проверить не более 3-ёх чисел. Для списка из 1024 элементов log₂1024 = 10, потому что 2¹⁰ == 1024. Следовательно, для списка из 1024 чисел придётся проверить не более 10-ти чисел.

Внимание В учебнике много говорится о логарифмах, поэтому нужно чётко представлять, что это такое. Если вы пока не очень хорошо разбираетесь в логарифмах, посмотрите отличное обучающее видео на YouTube:

Внимание Бинарный поиск работает только в том случае, если список отсортирован. Например, имена в телефонной книге хранятся в алфавитном порядке, и вы можете воспользоваться бинарным поиском. А что произойдёт, если имена не будут отсортированы по алфавиту?

Составим блок-схему для алгоритма Бинарного поиска

Используем массив int array[]; внутри которого будем искать число.
Зададим переменную int low = 0; - индекс первого элемента массива [0].
Зададим переменную int high = (sizeof(array) / sizeof(int)) - 1; - индекс последнего элемента массива.
На каждой итерации цикла, алгоритм проверяет средний элемент массива.
Зададим переменную int middle = (low + high) / 2; - Если значение суммы (low + high) нечётное, то C автоматически округляет значение middle в меньшую сторону.
Зададим переменную int guess = array[middle]; - переменная хранения вероятно искомого числа.
Если названное число было слишком мало, то переменная low обновляется соответственно по условию:
```
if (guess < item)
{
    low = middle + 1;
}
```
А если догадка была слишком велика, то обновляется переменная high:
```
if (guess > item)
{
    high = middle - 1;
}
```
Если значение найдено, то поиск завершён:
```
if (guess == item)
{
    return middle;
}
```
Поиск осуществляется до тех пор пока не будет найдено искомое число:
```
while (low <= high)
{
    guess == item;
}
```
В случаи если искомое число в массиве найдено - сообщим соответствующим текстом пользователю в консоль, указав индекс по которому расположено искомое число:
```
printf("Number is found at index [%d].", middle);
```
В случаи если искомое число в массиве не найдено - сообщим соответствующим текстом пользователю в консоль:
```
printf("No number in array.");
```
Массив для тестирования работы функции:
```
my_list[9] = {1, 3, 5, 7, 9, 10, 12, 19, 444};
```

Из готовых блоков кода, составим функцию поиска числа в сортированном массиве, принимающей три аргумента: собственно сам отсортированный массив чисел(константный указатель на него), реальная длина массива и искомое число:

#include <stdio.h>
#include <stddef.h> // работа с типом size_t
// Возвращает индекс найденного элемента или -1, если не найден
int binary_search(const int *array, size_t n, int item) // size_t n - реальный размер массива
{
    // Инициализация границ
    size_t low = 0;
    size_t high = (n == 0) ? 0 : n - 1; /* Если n == 0, никакой итерации быть не должно.
        Это дальше блокируем условием цикла (см. ниже) */
    // Условие цикла и вычисление середины
    while (n != 0 && low <= high) /* n != 0 — быстрый выход для пустого массива
        low <= high — классическое условие для бинарного поиска в фиксированном диапазоне */
    {
        // middle = low + (high - low)/2 — устойчивая формула без риска переполнения
        size_t middle = low + (high - low) / 2; 
        int guess = array[middle];        
        // Сравнение и смещение границ поиска
        if (guess == item) 
        {
            // Если попали — сразу возвращаем индекс
            return (int)middle; 
        }
        // Если искомое меньше guess, сдвигаем верхнюю границу влево
        else if (guess > item) 
        {
            if (middle == 0) /* Защита if (middle == 0) break; нужна потому, что 
                high = middle - 1 при middle == 0 и типе size_t (беззнаковый) сделало бы переполнение (огромное число). Это реже встречающаяся, но аккуратная защита */
            {
                break; // Досрочный выход из цикла
            }
            // защита от переполнения при middle-1, когда middle = 0
            high = middle - 1;
        }
        // Если искомое больше guess — сдвигаем нижнюю границу вправо
        else
        {
            low = middle + 1;
        }
    }
    return -1; // Результат, если не нашли. Возвращаем вне цикла — однозначный признак «не найден».
}

int main(void)
{
    int my_array[] = {1, 3, 5, 7, 9, 10, 12, 19, 444};
    size_t n = sizeof my_array / sizeof my_array[0]; /* Так правильно считать длину у реального массива 
        (пока мы ещё в той же области видимости, где он массив, а не указатель). */
    int my_guess = 5;
    int index = binary_search(my_array, n, my_guess); // вернёт индекс 2
    if (index >= 0)
    {
        printf("%d found at index [%d]\n", my_guess, index);
    }
    else
    {
        printf("%d not found\n", my_guess);
    }

    my_guess = 55;
    // вернёт -1
    index = binary_search(my_array, n, my_guess); 
    if (index >= 0)
    {
        printf("%d found at index [%d]\n", my_guess, index);
    }
    else
    {
        printf("%d not found\n", my_guess);
    }
    return 0;
}

Блок-схема алгоритма Бинарного поиска.

УПРАЖНЕНИЯ

Имеется отсортированный список из 256-ти имён, и вы ищете в нём значение методом Бинарного поиска. Какое максимальное количество проверок для этого может потребоваться?
Предположим, размер списка увеличился в два раза. Как изменится максимальное количество проверок?

Время выполнения

Сейчас мы погрузимся в основные концепции анализа алгоритмов и асимптотической нотации. В мире информатики крайне важно понимать, как алгоритмы работают с точки зрения времени и объёма памяти. Мы рассмотрим основные нотации, такие как Большое-O, Омега и Тета, подчеркивая их значение. К концу этой главы вы сможете оценивать сложность алгоритмов по времени выполнения и требуемого объёма памяти и понимать взаимосвязь между этими асимптотическими нотациями - в дальнейшем это станет основой для эффективного проектирования и оценки эффективности алгоритмов.

Всякий алгоритм - это вычислительный процесс. Процесс занимает время для его выполнения. Когда говорят об оптимизации процесса, то всегда есть два пути оптимизации: либо скорость выполнения, либо экономия памяти машины.

Алгоритм — это серия шагов для выполнения конкретной задачи или решения конкретной проблемы. Алгоритмы используются в различных областях, включая информатику, математику, инженерию и повседневное решение проблем. В информатике алгоритмы особенно важны для написания эффективных компьютерных программ. Такой подход к решению проблем является системным, предоставляющий чёткую и однозначную последовательность операций, которая, если следовать ей, приводит к желаемому результату. Эффективный алгоритм имеет следующие характеристики:

Чётко определённые действия: должен иметь точно определённые и недвусмысленные действия, которые являются ясными и понятными. Каждое действие должно иметь определённую цель.
Конечность: должен завершаться за конечное время.
Ввод: принимает входные данные.
Вывод: производит выходные данные.
Детерминированный: должен воспроизводить одни и те же выходные данные(результат) для одних и тех же входных данных каждый раз, когда выполняется.
Эффективность: должен решить проблему на основе баланса между затратами времени на подготовку алгоритма к его реализации и скорости получения результата.
Осуществимость: возможность реализации с использованием доступных ресурсов, таких как время, память и вычислительная мощность, имеющиеся в наличии у машины.
Корректность: должен выдавать правильный результат для всех допустимых входных данных.
Оптимальность: должен достигать наилучшего возможного решения с точки зрения использования времени и памяти. Оптимизированный алгоритм более эффективен, чем не оптимизированный. Поэтому оптимизированный алгоритм всегда предпочтительнее не оптимизированному.

Анализ алгоритмов

Это исследование, которое рассказывает об эффективности алгоритма. Эффективность измеряется с точки зрения времени и объёма памяти, которые алгоритм использует для решения конкретной задачи. Технические термины для анализа времени и объёма памяти, которые затрачивает алгоритм, – это временная сложность и сложность доступного объёма памяти соответственно.

Зачем анализировать алгоритмы?

Давайте проанализируем следующие две программы, которые вычисляют сумму n чисел. Вопрос заключается в следующем: какая из них лучше?

Напишем программу sumloop.c, которая вычисляет сумму чисел с помощью цикла:

#include <stdio.h>

void main()
{
    unsigned long long number = 0;
    printf("Enter the value of N: ");
    scanf("%llu", &number);

    unsigned long long sum = 0;
    unsigned long long iterator = 0;
    for (iterator = 0; iterator <= number; iterator++)
    {
        sum = sum + iterator;
    }
    printf(" The Summation is: %llu", sum);
}

Выполните программу. Обратите внимание - как долго она выполняется.

Результат вычисления суммы чисел с помощью цикла.

Теперь напишем программу sumformula.c, которая делает тоже самое но с помощью математической формулы. Данная формула являет собой реализацию алгоритма позволяющего находить сумму чисел:

#include <stdio.h>

void main()
{
    double number = 0;
    printf("Enter the value of N: ");
    scanf("%lf", &number);

    double sum = (number * (number - 1)) / 2;
    printf("The Summation is: %lf", sum);
}

Выполните программу. Обратите внимание - как долго она выполняется и какова точность проведённого вычисления.

Результат вычисления суммы чисел с помощью математической формулы.

Когда мы запускаем эти программы, первая программа занимает больше времени, чем вторая. Таким образом, вторая программа более эффективна. Должен существовать какой-то механизм для измерения эффективности программы и выбора лучшей.

Следующие ключевые моменты объясняют, почему необходимо анализировать алгоритмы:

Выбор алгоритма: Анализ алгоритмов помогает выбрать наиболее подходящий алгоритм для задачи перед его реализацией в виде программы.
Прогнозирование производительности: с помощью анализа алгоритма мы можем оценить время выполнения и использование памяти алгоритма до его фактической реализации.
Оценка эффективности: Анализ алгоритмов показывает эффективность различных алгоритмов в виде временной и пространственной сложности.
Улучшение дизайна: Анализ алгоритмов позволяет нам выявлять области для улучшения в дизайне и реализации алгоритма.
Масштабируемое поведение: Анализ алгоритмов помогает понять эффективность алгоритмов по мере увеличения размера входных данных. Это знание имеет решающее значение для эффективного решения проблем большого масштаба.
Исследования и инновации: Анализ алгоритмов является основополагающим в области исследований и инноваций в компьютерных науках. Он служит базой для разработки новых алгоритмов, улучшения существующих и углубления теоретического понимания эффективности алгоритмов.

Метод выражения временной и пространственной сложности алгоритма известен как асимптотическая нотация.

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

Используя асимптотические нотации, мы можем измерять наилучшие, средние и наихудшие случаи алгоритма, описанные следующим образом:

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

В общем, в асимптотическом анализе используются три обозначения: О-Большое, Омега и Тета.

Сколько времени нам сэкономит алгоритм Бинарного Поиска? Итак, без него, если в массиве сто элементов, то в худшем случаи нам нужно 100 попыток. Если в массиве четыре миллиарда (4000000000) элементов, то в худшем случаи - нам нужно совершить четыре миллиарда попыток. Грубо говоря, если нам нужно выполнить количество попыток равное размеру массива, и при увеличении размера количество попыток также увеличивается - то такой алгоритм всегда требует время выполнения называемое линейным.

С алгоритмом Бинарного Поиска ситуация иная. Мы уже на практике выяснили, что для массива из ста элементов, в худшем случаи нужно 7 попыток. Сколько нужно попыток для массива из 4000000000(четырёх миллиардов) элементов - не более 32-х.

Объединим в таблицу полученные знания относительно Линейного времени выполнения Простого алгоритма, и Логарифмического времени выполнения алгоритма Бинарного Поиска.

Время выполнения Простого и Бинарного алгоритмов поиска
Простой поиск	Бинарный поиск
100 элементов в массиве	100 элементов в массиве
100 попыток	7 попыток
4 000 000 000 элементов в массиве	4 000 000 000 элементов в массиве
4 000 000 000 попыток	32 попытки
O(n)	O(log₂n)
Линейное время выполнения	Логарифмическое время выполнения

O-Большое

Так записывают скорость работы алгоритма за Оптимальное время выполнения. Для чего нам эта информация? Дело в том, что иногда мы вынуждены будем применять готовые алгоритмы(написанные кем-то до нас), и потому крайне желательно понимать как быстро они работают(ну или приемлемо медленно ли).

Ещё раз: O-Большое представляет собой максимальное время, которое алгоритм может потратить на выполнение для данного размера входных данных. Он используется для представления худшего случая. Обозначается буквой O, произносимой как «Большое O». Временная сложность O(n) означает, что время выполнения алгоритма растёт линейным образом с увеличением размера входных данных, но не быстрее этого.

Пусть n - это входные данные алгоритма. T - это время, необходимое для решения задачи. Если f(n) - это входная функция, а C - это постоянная, то g(n) связано с f(n) по уравнению (f(n) = O g(n)). Время и память, используемые алгоритмом, всегда положительны, следовательно, f(n) и g(n) всегда положительны. Значение постоянной C зависит от таких переменных, как скорость процессора, объем памяти, язык программирования и т.д. Смотрите рисунок ниже:

Отношение между f(n) и g(n) в Большом O. Рисунок показывает, что после определённого значения k, C, функция g(n) всегда будет больше функции f(n).

f(n) = O g(n) - Уравнение (1)

Уравнение (1) можно трактовать как то, что f от n является Большим О от g от n. Его также можно записать с помощью уравнения (2), вставив константу C:

f(n) <= C.g(n) - Уравнение (2)

Уравнение (2) верно для каждого n, где n >= k, так что:

C > 0,

n >= k,

k >= 0

Здесь C и k - это две положительные константы, при этом значение C всегда больше 0 (ноль), то есть C > 0, а значение k может быть или не быть больше нуля, то есть k >= 0.

Пример 1: Найдите k и C для функций f(n) = n + 10 и g(n) = n.

Итак, f(n) = O g(n)

Также, f(n) <= C.g(n)

Подставьте значение функции:

Значит, (n + 10) <= C.n по Уравнению (1)

Чтобы удовлетворить это уравнение, давайте выберем:

C = 1 и n = k = 0, и подставьте эти значения в предыдущее уравнение (1), затем

0 + 10 <= 1 * 0

10 <= 0, это условие не выполнено.

Давайте выберем C = 2, n = k = 10, тогда уравнение (1) примет следующий вид:

20 <= 20

Таким образом, для C = 2 и k >= 10 функция g(n) всегда будет больше функции f(n), как показано на Рисунке, и функция f(n) в терминах большого O представляется следующим образом:

(n + 10) = O(n)

Пример 2: Представьте f(n) = 3n² + n + 10 и g(n) = n² в нотации Большого O.

Как мы знаем, f(n) <= C.g(n), согласно Уравнению (1)

(3n² + n + 10) <= C.(n²)

Теперь, чтобы удовлетворить предыдущее уравнение, рассмотрим C = 5, n = k = 2 и подставим в предыдущее Уравнение (1)

12 + 2 + 10 <= 5 * 4

24 <= 20,

Условие не выполнено. Поэтому, примем C = 5, теперь возьмем n = 3 = k = 3. Подставив значения в Уравнение (1), мы получаем следующее:

40 <= 45,

Итак, для C = 5 и n >= 3

(3n² + n + 10) <= C.(n²) или можно сказать:

(3n² + n + 10) = O(n²)

Как выбрать значение C и k?

Замените все термины в выражении на термин с высшей степенью (доминирующий термин); выражение 3n² + n + 10 можно записать как 3n² + n² + n². Сложите все термины, что даст 5n². Коэффициент этого термина равен 5. Таким образом, примите значение C равным 5. Теперь выражение (3n² + n + 10) = O(n²) можно записать как (3n² + n + 10) <= 5.(n²) согласно определению Большого O.

Для n = 1, выражение становится следующим:

(3.1² + 1 + 10) <= 5.(1²)

14 <= 5, что неверно

Для n = 2

(3.2² + 1 + 10) <= 5.(2²)

23 <= 20, что неверно

Для n = 3

(3.3² + 1 + 10) <= 5.(3²)

38 <= 45, что верно

Начиная с n = 3, значение f(n) всегда будет меньше или равно C.g(n), поэтому выберите это как значение k = 5.

Омега

Представляет собой нижнюю временную границу (минимум или не менее) алгоритма для решения проблемы. Это представляет лучший случай. Это описывает минимально возможное время, за которое алгоритм может выполнить задачу для заданного размера входных данных. Обозначается омега ( Ω ). См. Рисунок ниже:

Отношение между f(n) и g(n) в Омега.

На рисунке выше показано, что после определённого значения k, C, функция g(n) всегда будет меньше f(n). Это можно выразить Уравнениями (1) и (2) ниже:

f(n) = Ω g(n) Уравнение (1)

f(n) >= C.g(n) Уравнение (2)

Уравнение (2) верно для каждого n, где n >= k

так что:

C > 0

n >= k

k >= 0

Пример 3: Выразите функцию f(n) = 3n² + n через Омега.

Нам нужно найти g(n). Выберем g(n) = n², так как это доминирующий член в f(n) = 3n² + n. Согласно определению Омега:

f(n) >= C.(n²) положим C = 3

3n² + n >= 3n², по Уравнению (1)

n >= 3n² - 3n²

n >= 0

Проверьте, подставив n = 2

3.2² + 2 >= 3.2²

14 >= 12

Таким образом, для всех значений n >= 0 и C = 3 условие 3n² + n >= 3n² верно, поэтому мы можем выбрать значение k, равное n. Функция в терминах Омега записывается следующим образом:

f(3n² + n) = Ω g(n²)

Тета

Представляет собой точное время, которое алгоритм затрачивает на решение задачи. Используется для представления среднего случая. Это говорит нам о точной скорости, с которой алгоритм будет работать по мере увеличения размера входных данных. Обозначается Тетой ( Θ ). См. Рисунок ниже:

Отношение между f(n) и g(n) в Тета.

Рисунок выше показывает, что после определенного значения k, C, функция f(n) всегда будет находиться между C2.g(n) и C1.g(n). Это выражается Уравнением (1) ниже:

Θ.g(n) <= f(n) <= Θ.g(n) Уравнение (1)

Для C1 и C2 это также можно записать следующим образом:

C1.g(n) <= f(n) <= C2.g(n)

для всех n >= k.

Пример 4: Выразите f(n) = 3n² + n в Тета.

Чтобы представить f(n) = 3n² + n в тета-нотации, нам нужно найти два константных значения C1, C2 и k, такие как:

C1 * g(n) <= f(n) <=C2 * g(n) для всех n >= k,

где g(n) представляет более простую функцию.

Давайте проанализируем функцию f(n) = 3n² + n.

Нижняя граница:

Нам нужно найти функцию g(n) такую, что C1 * g(n) <= f(n) для всех n >= k.

Выбор g(n) = n² должен сработать. Итак, у нас есть следующее:

C1 * n² <= 3n² + n.

Упрощая, мы получаем следующее:

C1 <= 3 + 1/n.

Когда n стремится к бесконечности, 1/n приближается к 0 (нулю), поэтому мы можем это игнорировать. Таким образом, мы можем выбрать C1 = 3.

Верхняя граница:

Нам нужно найти g(n) так, чтобы f(n) <= C2 * g(n) для всех n >= k. Выбор g(n) = n² должен сработать. Итак, у нас есть следующее:

3n² + n <= C2 * n².

Упрощая, мы получаем следующее:

3 + 1/n <= C2.

По мере того как n стремится к бесконечности, 1/n стремится к 0, поэтому мы можем его игнорировать. Таким образом, мы можем выбрать C2 = 4.

Таким образом, мы нашли C1 = 3 и C2 = 4, и мы можем выбрать k = 1. Следовательно, выразите f(n) = 3n² + n в нотации Θ (Тета) следующим образом:

Давайте проверим, подставив n = 2 в C1 * g(n) <= f(n) <=C2 * g(n)

3.2² <= 3.2²+2 <= 4.2²

12 <= 14 <=16,

Что является истинным условием.

Почему Большое O?

Нотация Большого O обычно предпочтительнее других асимптотических нотаций по следующим причинам:

Простота: Нотация Большого O (Big-O) предоставляет простой способ описания верхней границы алгоритма или поведения в худшем случае. Она объясняет, как производительность алгоритма зависит от размера входных данных, что позволяет легко сравнивать и анализировать.
Упор на верхнюю границу: Это подчеркивает верхнюю границу. Это гарантирует, что алгоритм не будет работать хуже определенной нормы, что позволяет нам принимать обоснованные решения о его масштабируемости и ресурсных требованиях.
Стандартизация: Информатика приняла нотацию Большое-O в качестве стандартной нотации. Она широко используется и понятна, что упрощает для исследователей, разработчиков и студентов сравнение эффективности различных алгоритмов.

Время выполнения алгоритмов растёт с не одинаковой скоростью.

Пример

Например, вы пишите алгоритм поиска для NASA. От его эффективности зависит успех посадки космического корабля на поверхность Марса. Согласно программе, ваш алгоритм вступает в работу при подлёте к Марсу.

Ещё на стадии выбора вами между простым и Бинарным алгоритмами, вы должны были ориентироваться на быстроту и правильность выполнения вашего алгоритма. С одной стороны - Бинарный поиск работает быстрее. Расчёты в симуляторе полёта показали, что времени на посадку есть не более 10 секунд, и если не вложится в эти ограничения, - момент может быть упущен - это очень опасно и дорого обойдётся всей миссии.

С другой стороны Простой поиск, проще написать, вероятность допустить ошибку в коде меньше.

Ещё здесь на Земле, вы должны проверить скорость работы обоих алгоритмов, что бы принять окончательное решение - какой применить.

Допустим, проверка одного элемента из массива с помощью Простого поиска составляет 1 миллисекунду (1/1000 сек). Значит для проверки 100 элементов из массива, будет потрачено не менее 100 миллисекунд (1/10 сек).

Бинарный поиск позволяет сделать тоже самое за 7 миллисекунд - это минимум в 14 раз быстрее. Так как здесь уже работает логарифмическое время O(log₂n). Хорошо, но нужно например проверить 1500000000(полтора миллиарда) элементов в массиве. Сколько времени займёт выполнение у Простого и Бинарного алгоритмов поиска?

С Простым поиском всё понятно, он линейный: 1 500 000 000 / 1000(1000 элементов в 1 секунду) = 1 500 000 секунд, это 17 с половиной дней!

Логарифмическое время Бинарного алгоритма поиска вычисляем так log₂1500000000 = ? Кстати в языке С в заголовочном файле <math.h> есть функция log2(), которая как раз вычисляет логарифм по основанию 2, и аргументом принимает число. Напишем маленькую программу для вычисления необходимого нам логарифмического времени:

#include <stdio.h>
#include <math.h>

int main(void)
{
    unsigned long int elements = 1500000000;
    printf("\nWe need %.3f ms to found number in array\n", log2(elements));

    return 0;
}

Результат:

30-ть с половиной миллисекунд! В 10 секунд отведённого времени мы точно вложимся.

Сравним изменение скорости выполнения для Простого и Бинарного алгоритмов поиска:

Время выполнения увеличивается совершенно с разной скоростью.
Простой поиск	Бинарный поиск
100 элементов = 100 мс	7 мс
10 000 элементов = 10 с	14 мс
1 500 000 000 элементов = 17.36 дней	30.482 мс

Очевидно - Увеличение количества элементов в массиве на Бинарный поиск влияет не значительно. Простой поиск же тратит времени выполнения алгоритма просто гораздо больше. Т.о. Бинарный поиск с ростом количества элементов работает всё быстрее, а Простой - всё медленнее.

Ради интереса, точнее ради миссии высадки на Марс, проверим во сколько раз Бинарный поиск быстрее Простого:

1500000 секунд / 30 миллисекунд (0.030 секунд) = В 50 000 000 раз быстрее. Думаю этим всё сказано. Вы хорошо проверили оба алгоритма в лаборатории NASA, и результаты исследований стоит представить команде.

О-Большое описывает, на сколько алгоритм быстрый, и дело совсем не в секундах или миллисекундах, днях или годах,- O(n) не измеряет время в конкретных его единицах, оно показывает, насколько быстро возрастают затраты времени на выполнение алгоритма.

Ещё один пример

Для проверки списка размером n Бинарному алгоритму поиска требуется log₂n операций. Запишем О-большое так: O(log₂n). В общем случае О-большое выглядит так: O(n), где О-большое - Оптимальное время выполнения алгоритма зависящее от (n) - количества Операций.

Визуализация большого О

Возьмём квадрат, наша задача поделить его на 16 маленьких квадратов.

Какой алгоритм хороший для построения этой сетки?

Алгоритм №1

Как вариант можно нарисовать 16 квадратов, по одному за раз. Напоминаю: «O-большое» подсчитывает количество операций. В данном примере рисование квадрата считается одной операцией. Нужно нарисовать 16-ть квадратов. Сколько операций по рисованию одного квадрата придётся выполнить?

По одному за раз - 16 операций.

Как выглядит время выполнения этого алгоритма? Просто, оно линейное O(n).

Алгоритм №2

Можно сделать иначе, так сказать от двух-мерного решения, перейти к трёх-мерному. Сложить лист пополам, ещё раз пополам, ещё раз пополам, ещё раз пополам.

Каждая операция удваивает количество прямоугольников и в итоге мы получаем 16 квадратов на листе.

Как выглядит время выполнения этого алгоритма? Оно логарифмическое O(log₂n), O(log₂16) = 4. Развернув лист, мы увидим сетку граней рисующих 16-ть квадратов.

O-большое определяет время выполнения алгоритма в худшем случае

Если мы просматриваем телефонный справочник, и нам нужна последняя запись в нём - это худший сценарий работы со справочником. Так как мы должны просмотреть каждую запись, прежде чем доберёмся до последней - это O(n) случай. Если же нам нужен первый номер телефона в справочнике, то мы находим его с первого шага - это O(1) случай. O(n) это худший случай, O(1) это лучший случай. Следовательно O(n) гарантирует нам, что дольше искать уже не возможно.

Кроме худшего и лучшего случаев, есть ещё и средний случай - кода время выполнения занимает среднюю продолжительность(об это далее).

O-большое, пять видов

O(log₂n), или логарифмическое время. Пример: бинарный поиск.
O(n), или линейное время. Пример: простой поиск.
O(n * log n). Пример: эффективные алгоритмы сортировки (быстрая сортировка — но об этом далее).
O(n²). Пример: медленные алгоритмы сортировки (сортировка выбором — см. далее).
O(n!). Пример: очень медленные алгоритмы (задача о коммивояжере — о ней будет рассказано в следующем разделе).

Зависимость Времени выполнения t от Количества операций q
Количество прямоугольников	O(log₂n)	O(n)	O(n * log₂n)	O(n²)	O(n!)
16	0.4 сек	1.6 сек	6.4 сек	25.6 сек	66301 лет
256	0.8 сек	25.6 сек	3.4 мин	1.8 часов	2.7*10⁴⁹⁸ лет
1024	1.0 сек	1.7 мин	17 мин	1.2 дня	1.7*10²⁶³¹ лет
График

Примеры:

O(1) - Константная временная сложность: Независимо от размера входных данных, алгоритм выполняется за постоянное время. Доступ к элементу массива в памяти машины по его индексу.
O(log₂n) - Логарифмическая временная сложность: Размер входных данных имеет логарифмическое влияние на время, например, при бинарном поиске.
O(n) - Линейная временная сложность: Время выполнения растёт линейно с увеличением размера входных данных. Например, итерация по массиву для поиска конкретного элемента.
O(n log n) - Логарифмически-линейная сложность по времени: Время выполнения растёт линейно, умноженное на логарифм размера входных данных. Например, эффективные алгоритмы сортировки, такие как сортировка слиянием и быстрая сортировка.
O(n²) - Квадратичная временная сложность: Время выполнения растёт квадратично с размером входных данных. Например, вложенные циклы проходят по 2D массиву.
O(2ⁿ) - Экспоненциальная временная сложность: Время выполнения растёт экспоненциально с увеличением размера входных данных. Например, генерация всех подмножеств множества.

Итак, эти пять вариантов времени выполнения встречаются чаще всего, хотя есть и другие. На практике «O-большое» не удается легко преобразовать в количество операций с такой точностью, но пока нам хватит и этого. Мы вернёмся к «O-большому» после рассмотрения ещё нескольких алгоритмов.

УПРАЖНЕНИЯ

Приведите время выполнения «O-большое» для каждого из следующих сценариев:

Известна фамилия, нужно найти номер в телефонной книге.
Известен номер, нужно найти фамилию в телефонной книге. (Подсказка: вам придется провести поиск по всей книге!)
Нужно прочитать телефоны всех людей в телефонной книге.
Нужно прочитать телефоны всех людей, фамилии которых начинаются с буквы «А». (Вопрос с подвохом! В нем задействованы концепции, которые более подробно рассматриваются далее. Прочитайте ответ — скорее всего, он вас удивит!)

Заключение

Скорость алгоритмов измеряется не в секундах, а в темпе роста количества операций.
По сути, формула описывает, насколько быстро возрастает время выполнения алгоритма с увеличением размера входных данных.
Время выполнения алгоритмов выражается как «O-большое».
Время выполнения O(log₂n) быстрее O(n), а с увеличением размера списка, в котором происходит поиск значения, оно становится намного быстрее.

Измерение сложности на основе затрат памяти машины

Как и временная сложность, также выражается с использованием нотации Большого O. Помогает понять, как увеличивается использование памяти алгоритмом с ростом размера входных данных:

O(1) - Постоянная сложность: Алгоритм использует фиксированный объём памяти независимо от размера входных данных. Например, обмен значениями между переменными.
O(n) - Линейная сложность: Использование памяти растёт линейно с размером входных данных. Например, создание массива для хранения входных элементов.
O(n²) - Квадратическая сложность: Использование памяти растёт квадратично с увеличением размера входных данных. Например, создание двумерной матрицы(таблицы).
O(2ⁿ): Экспоненциальная сложность: Использование памяти возрастает экспоненциально с размером входных данных. Например, генерация всех подмножеств множества.

Анализ сложности по объёму памяти особенно важен при работе с большими входными данными или в условиях ограниченной памяти, таких как системы на основе микроконтроллеров.

Отношение между асимптотическими обозначениями Большого-O

Если алгоритм выполняется за постоянное время, то он не зависит от длины входных данных n, тогда как линейное время линейно зависит от входных данных. Например, если мы увеличиваем размер n, время будет увеличиваться соответственно. Связь между асимптотическими обозначениями выглядит следующим образом:

O(1) < O(log₂n) < O(n) < O(n log₂n) < O(n²) < O(n³)

Сравнение Большого O для различных значений входных данных (n).
n	O(1)	O(log₂n)	O(n)	O(n log₂n)	O(n²)	O(n³)
1	1	0	1	0	1	1
2	1	1	2	2	4	8
3	1	1.58	3	4.78	9	27
4	1	2	4	8	16	64
5	1	2.32	5	11.6	25	125
6	1	2.58	6	15.48	36	216

Для графического изображения предыдущей таблицы смотрите рисунок ниже:

Соотношение между объёмом памяти, занимаемым кодом, и размером входных данных.

Задача о коммивояжере

Возможно, после прочтения предыдущего раздела вы подумали: Уж мне то точно не попадется алгоритм с временем O(n!). Ошибаетесь, и вот почему! Рассмотрим алгоритм с ужасно плохим временем выполнения. Это известная задача из области теории вычислений, в которой время выполнения растёт просто с ужасающей скоростью, и некоторые очень умные люди считают, что с этим уже ничего не поделать. Она называется задачей о коммивояжере.

Задача коммивояжера простая - посетить несколько городов. Но сложность её в вот в чём - сделать это нужно в кратчайшие сроки по времени. Казалось бы что тут "ужасающе сложного"? Посетил один город, отправился в следующий ближайший, и так все и объедешь... Да, но...

Давайте проследим за нашим коммивояжером. Как он будет готовится к путешествию - ведь товары сами себя не продадут. Посетить нужно всего 5 городов. Представим их как пять точек на карте Страны:

5 городов, какой маршрут самый короткий? Нужно объехать все города за минимальное время.

Планируя поездку, коммивояжер может подготовиться - сесть и просчитать длину всех маршрутов заранее, и сравнив итоговые расстояния - выбрать самый короткий. Это рациональный подход к делу. Посмотрим, что получится у продавца полезных товаров?

Допустим он начал просчитывать маршруты так:

Маршрут №1 - **1200** километров. Маршрут №2 - **1030** километров. Маршрут №3 - **1333** километров.

Очевидно что для пяти городов - маршрутов не 3, не 5, и даже не 50. Их 5! (пять факториал). Факториал 5 равен = 5 * 4 * 3 * 2 * 1 = 120 вариантов маршрутов.

Составим таблицу количества вариантов маршрутов, при увеличении количества городов которые должен посетить на коммивояжёр:

Количество вариантов маршрутов в зависимости от количества городов для посещения.
Городов в маршруте	Вариантов маршрутов в путешествии
1	0
2	1
3	6
4	24
5	120
6	720
7	5 040
8	40 320
9	362 880
10	3 628 800
25	15 511 210 043 330 985 984 000 000

Иными словами, как говорят программисты - Количество операций стремительно растёт.

В общем случае для вычисления результата при n элементах потребуется n! ( n-факториал ) операций. А значит, время выполнения составит O(n!) (такое время называется факториальным). При любом сколько-нибудь серьезном размере списка количество операций будет просто ошеломительным. Скажем, если вы попытаетесь решить задачу для ста или более городов, сделать это за время трёхнедельного отпуска не удастся — к тому времени Вселенная уже закончит своё существование.

Для нашего продавца товаров нужен совсем другой алгоритм поиска оптимального маршрута. Но какой? Сколько бы ни пытались математики, программисты, и все коммивояжёры вместе взятые на всей Земле найти такой алгоритм, - похоже, что его не существует... Однако возможно надежда есть - использовать не точный, а приближённый алгоритм, но о нём далее.

Шпаргалка

Бинарный поиск работает намного быстрее простого.
Время выполнения O(log n) быстрее O(n), а с увеличением размера списка, в котором происходит поиск значения, оно становится намного быстрее.
Скорость алгоритмов измеряется не в секундах - в сложности, то как возрастают затраты времени выполнения при увеличении числа элементов обрабатываемым алгоритмом.
Время выполнения алгоритма описывается ростом количества операций.
Время выполнения алгоритмов выражается как «O-большое».

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

В этой главе

Вы познакомитесь с массивами и связанными списками — двумя основными структурами данных, которые используются буквально везде. Мы уже применяли массивы выше и будем говорить о них почти в каждой главе книги. Массивы чрезвычайно важны, уделите им внимание! Впрочем, иногда вместо массива лучше воспользоваться связанным списком. В этой главе объясняются плюсы и минусы обеих структур данных, чтобы вы могли решить, какой вариант лучше подходит для вашего алгоритма.
Вы изучите свой первый алгоритм сортировки. Многие алгоритмы работают только с отсортированными данными. Помните бинарный поиск? Он применяется только к предварительно отсортированному списку. В большинстве языков существуют встроенные алгоритмы сортировки, так что вам редко приходится писать свою версию «с нуля». Однако алгоритм сортировки выбором поможет перейти к алгоритму быстрой сортировки, описанному далее. Алгоритм быстрой сортировки очень важен, и вам будет проще разобраться в нем, если вы уже знаете хотя бы один алгоритм сортировки.

ЧТО НЕОБХОДИМО ЗНАТЬ Чтобы понять ту часть этой главы, которая относится к анализу эффективности, необходимо понимать смысл понятия «O-большое» и логарифмов. Если вы совершенно не разбираетесь в этих вопросах, лучше вернуться и прочитать о них снова, посмотреть видео-уроки. «O-большое» будет постоянно использоваться в оставшихся главах книги.

Принцип работы памяти

Ещё раз о памяти машины. Представьте, что вы пришли в театр и хотите оставить свои личные вещи в гардеробе. Для хранения вещей есть специальные ящики. В каждом ящике помещается один предмет:

Вы хотите сдать на хранение две вещи, поэтому требуете выделить вам два ящика:

Вы оставляете свои две вещи: Зонтик и Пончик:

Теперь, когда ваши вещи сохранены в ящиках гардеробного комода - можно идти смотреть спектакль.

Вот и всё - вы теперь знаете как работает память вычислительной машины! Давайте вспомним ключевые детали работы и организации памяти. Ну во-первых - у каждого ящика свой шестнадцатиричный адрес имеется. Т.е. каждая ячейка в памяти имеет свой личный адрес, например такой: 0xfc08a35eb.

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

Массивы и связанные списки

Иногда в памяти требуется сохранить список элементов. Предположим, вы пишете приложение для управления текущими делами. Описания задач должны храниться в виде списка в памяти.

Что использовать — массив или связанный список? Для начала попробуем сохранить задачи в массиве, потому что этот способ более понятен. При использовании массива все задачи хранятся в памяти непрерывно (то есть рядом друг с другом).