Link: 1 – Сложность алгоритмов

Несмотря на название курса, я думаю будет интересен многим, особенно самоучкам таким как я

Начинается этот курс с лекции по Сложности алгоримов, в котором кстати будут задеты и структуры данных такие как Queue & Stack, но об этом позже…

Сложность алгоритмов

Видео начинается с вопроса как можно изменить сложность алгоритма – лучше всего это делать с помощью количества операций, в зависимости от размера входных данных.
n – размер входа (10 / 100 / 100000000)

(1)   \begin{equation*}  534n^3+16n^2+252 \end{equation*}

Преподаватель поднимает интересный вопрос “А что считать операцией?”. По сути компьютер может делать больше/меньше операций, чем мы думаем

Например, сложение 64-битных чисел 32-битным процессором

(2)   \begin{equation*}  2n^4+10 \end{equation*}

Какая программа лучше 1 или 2?
Слишком трудоемко оценивать количество операций точно, а во-вторых для достаточно больших входах коэффициенты не играют существенной роли по сравнению со степенью, в которую мы возводим n

  1. Будем оценивать наиболее быстро растущую часть (с наибольшей степенью)
  2. Коэффициент игнорируем

Возьмем такие примеры

n
n^2
n^3
2^n

Во сколько раз увеличится количество операций, если n увеличить в 10 раз?

n – в 10
n^2 – в 100
n^3 – в 1000
2^n – а это вообще кошмар, если мы увеличим n НА 10, то уже тогда количество операций увеличится В 1024

Первые 3 программы работаю за полином (т.к. их сложность увеличивается n^k где k - const) или у них полиномиальное время работы
В то время как 4 программа за экспоненциальное время

Настало время вспомнить что такое Логарифм
Показатель степени, в которую надо возвести число, называемое основанием, чтобы получить данное число.
И некоторые правила:

log_{a}a^x = x
log_{a}1 = 0
log_{a}xy = log_{a}x +log_{a}y
log_{b}z = log_{a}z \cdot log_{b}a

А log_{b}a – это коэффициент(не зависит от n), от который мы, по второго правилу, не учитываем.
Получается, что если в оценке сложности будет логарифм, то не имеет значение по какому основанию этот логарифм.

Следующая порция функций из разряда “Опреди что быстрее”?

n logn
n^2
n \sqrt{n}

logn работает быстрее чем n в любой степени

Еще один интересный вопрос

n^{100}
2^n

Что лучше на практике? первая или вторая?
Теоретически вторая формула хуже, но в настоящее время у нас нету таких компьютеров, на которых мы бы смогли вычислять настолько большие числа, при которых это становилось бы заметно, поэтому на практике выбирают первую программу.

В конце первой части преподаватель упоминает сортировку пузырьком и оценивает его сложность как n^2

Структуры данных (26:20)

Упоминается массив. Он как бы не совсем структура данных, а скорее конструкция языка, благодаря которой можно создавать другие структуры.

Линейные структуры данных (28:00)

Stack (Стек/LIFO) (29:00)

В общих чертах (практически без кода) рассказывает про стек. Приводит пример “Правильной скобочной последовательности” (эхх, если бы я знал про это на олимпиаде по информатике, вся жизнь сложилась бы иначе)

Queue (Очередь/FIFO) (39:10)

Небольшой рассказ об очереди

Пример реализации stack (41:20)

Пример реализации queue (49:40)

Циклическая очередь (53:50)

Проблема очереди, сделанной на массиве, в том что размер массива зависит от количества записей и доставаний из очереди, а не от размера самой очереди

Очередь с 2 концами (58:50)

Очередь в которую можно класть и забирать из обоих концов

List (Списки) на статической памяти (01:07:50)

Недостатки

  • Теряется общность
  • Приходится писать больше кода
  • Заранее задается длинна списка (прим от автора)

Плюсы:

  • Простота отладки
  • Увеличение скорости работы

Односвязны список (01:12:50)

Фиктивная голова (01:20:10)

Удобно при добавлении в обе стороны списка. Нет необходимости при реализации Stack

Двухсвязный список (01:29:15)

Мультисписок (01:34:55)

Если мы удаляем элемент, то у нас остается дырки в массиве. Чтобы для этого избавиться необходимо создать стек свободных ячеек. Класть туда при удалении и забирать оттуда при добавлении элемента