These are memory prompts that I wrote while studying the topic. cd
Q: Расскажи об Big O notation
A: О большое показывает лишь динамику изменения вычислительной сложности алгоритма(то бишь зависимость этой динамики от размера входных данных n).
Big O показывает верхнюю границу оценки алгоритма, то есть соответствует худшему случаю работы алгоритма в вычислительном плане. А худший случай работы алгоритма это когда n равен бесконечности. Тогда получается что даже если к n прибавить константу любой величины, то асимптотически всё равно получится та же бесконечность.
По сути О большое показывает лишь скорость/динамику роста сложности алгоритма, а не его фактическое время выполнения.
Q: Можно ли отбрасывать переменные n/m помимо констант C?
A: Отбрасывать мы можем только константы, но не переменные. Почему? Потому что переменные связаны с размерностью входных данных.
Q: O(1) это какое время? Расскажи о нем.
A: Это константное время, не зависящее от размера данных. 1 значит одна операция ⇒ не имеет значения размер данных на вход. Выполняться он будет всегда мгновенно, например обращение к элементу массива по индексу.
Q: O(n) это какая сложность? Расскажи о ней.
A: Линейное время. Сложность работы алгоритма зависит от размера входных данных – то есть отn
Q: Назови правило отбрасывания константы
A: O(1 + n) = O(n) Любая константа которая прибавляется к n отбрасывается. Почему? Потому что Big O показывает верхнюю границу оценки алгоритма, то есть соответствует худшему случаю работы алгоритма в вычислительном плане. А худший случай работы алгоритма это когда n равен бесконечности. Тогда получается что даже если к n прибавить константу любой величины, то асимптотически, — всё равно получится та же бесконечность.
Q: O(n^2) — что это за сложность? Объясни на примерах.
A: Квадратичная сложность. Время работы растёт пропорционально квадрату размера входных данных (n * n). Примеры:
- Сортировка пузырьком (Bubble Sort) — сравнение каждого элемента с каждым.
- Вложенные циклы (например, перебор всех пар в массиве).
Почему важно: На больших данных (n=10 000→ 100 млн операций) такие алгоритмы становятся крайне медленными.
Q: What about O(n^2 + A) - what should we do with A
A: When there is an unknown variable - it has to stay as it is. It can be anything. So, as a rule of thumb, we keep it as it is.
Q: Расскажи про O(log n)
A: Это логарифмическая сложность, присущая бинарному поиску. Там, где происходит иерархическое разбиение данных и последующая обработка оставшихся частей, как правило, логарифмическая сложность алгоритмов.
Q: A: