Привет!
Сегодняшняя лекция будет немного отличаться от остальных. Отличаться она будет тем, что имеет лишь косвенное отношение к Java.
Тем не менее, эта тема очень важна для каждого программиста. Мы поговорим об алгоритмах.
Что такое алгоритм?
Говоря простым языком, это некоторая последовательность действий, которые необходимо совершить для достижения нужного результата.
Мы часто используем алгоритмы в повседневной жизни.
Например, каждое утро перед тобой стоит задача: прийти на учебу или работу, и быть при этом:
- Одетым
- Чистым
- Сытым
- Проснуться по будильнику.
- Принять душ, умыться.
- Приготовить завтрак, сварить кофе/заварить чай.
- Поесть.
- Если не погладил одежду с вечера — погладить.
- Одеться.
- Выйти из дома.
- Купить или скачать в Интернете “Словарь русских личных имен” 1966 года издания.
- Находить каждое имя из нашего списка в этом словаре.
- Записывать на бумажку, на какой странице словаря находится имя.
- Расставить имена по порядку, используя записи на бумажке.
for
, который выполняет эту задачу
int[] numbers = new int[100];
// ..заполняем массив числами
for (int i: numbers) {
System.out.println(i);
}
Какая сложность у написанного алгоритма? Линейная, O(N).
Число действий, которые должна совершить программа, зависит от того, сколько именно чисел в нее передали.
Если в массиве будет 100 чисел, действий (выводов на экран) будет 100. Если чисел в массиве будет 10000, нужно будет совершить 10000 действий.
Можно ли улучшить наш алгоритм? Нет.
Нам в любом случае придется совершить N проходов по массиву и выполнить N выводов в консоль.
Рассмотрим другой пример.
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(0, 20202);
numbers.add(0, 123);
numbers.add(0, 8283);
}
У нас есть пустой LinkedList
, в который мы вставляем несколько чисел. Нам нужно оценить сложность алгоритма вставки одного числа в LinkedList
в нашем примере, и как она зависит от числа элементов, находящихся в списке.
Ответом будет O(1) — постоянная сложность. Почему?
Обрати внимание: каждый раз мы вставляем число в начало списка. К тому же, как ты помнишь, при вставке числа в LinkedList
элементы никуда не сдвигаются — происходит переопределение ссылок (если вдруг забыл, как работает LinkedList, загляни в одну из наших старых лекций).
Если сейчас первое число в нашем списке — число х
, а мы вставляем в начало списка число y, все, что для этого нужно:
x.previous = y;
y.previous = null;
y.next = x;
Для этого переопределения ссылок нам неважно, сколько чисел сейчас в LinkedList
— хоть одно, хоть миллиард.
Сложность алгоритма будет постоянной — O(1).
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ