Когда мы говорим об алгоритмах, то нам бы очень хотелось понять, как быстро он будет работать? При этом, время выполнения алгоритма, не может быть объективным критерием, так как на разных “машинах” и на разных входных данных время может меняться критически. Именно поэтому в теории алгоритмов вводится понятие Big O. С помощью этого значения мы определяем эффективность того или иного решения проблемы.
И вместо времени выполнения мы начинаем думать о том, какое соотношение времени выполнения к входным данным. При этом, размер входных данных мы обозначаем, как n.
Таким образом, если время выполнения напрямую зависит от размера входных данных, то эта ситуация выражается математически, как O(n). Если мы, по какой-либо причине, решили сравнить каждое значение с каждым, то сложность будет n*n. Эта ситуация выражается, как O(n^2) (n в квадрате).
Также стоит учитывать, что иногда наш алгоритм может “медленно” работать при маленьком размере входных данных, но, с ростом этого размера, он будет работать “быстрее”, чем алгоритм, работающий быстрее на маленькой выборке.
Следовательно, наш анализ является асимптотическим, т.е. мы анализируем рост сложности алгоритма с ростом размера входных данных.
Для лучшего понимания, рассмотрим несколько примеров:
void printDevelopers(Developer[] developers) {
for (int i = 0; i < developers.length; i++) {
System.out.println(developers[i]);
}
}Сложность данного примера – O(n), так как мы всегда должны обратиться к каждому элементу массива. Если мы передадим 1_000_000 элементов в массиве, мы обратимся 1 000 000 раз.
void printAllNumberPairs(int [] numbers) {
for(int i = 0; i < numbers.lenght; i++) {
for(int j = 0; j < numbers.length; j ++) {
System.out.println(numbers[i] + " " + numbers[j]);
}
}
}Сложность данного алгоритма – O(n^2), так как мы должны вывести пары “каждый элемент с каждым”. Если мы передадим 10 элементов, то мы должны будем 100 раз обратиться к массиву.
void printNumberByIndex (int [] numbers, int index) {
System.out.println(numbers[i]);
}Cложность данного алгоритма – O(1), так как независимо от размера массива, мы всегда обращаемся 1 раз.
Анализ коэффициентов
Рассмотрим следующий пример:
void printNumbersTwice(int [] numbers) {
for(int i = 0; i < numbers.lenght; i++) {
System.out.println(numbers[i]);
}
for(int j = 0; j < numbers.lenght; j++) {
System.out.println(numbers[j]);
}
}Т.е. если мы передадим 100 элементов в массиве, то обратимся к массиву 200 раз, если 500 – 1000. Получается, что сложность данного метода – O(2n), но, при анализе алгоритма, мы никогда не учитываем коэффициенты. И сложность данного метода будет выражена, как O(n).
Всегда учитывается “худший” случай
int findIndexByValue (int [] numbers, int value) {
for(int i = 0; i < numbers.length; i++) {
if(numbers[i] == value) {
return i;
}
}
return -1;
}В данном случае, если в массиве числа от 1 до 100 и мы ищем 1, то мы обратимся к массиву только 1 раз. Но, в худшем случае, мы ищем 101, которого нет в массиве и в этом случае мы обратимся 100 раз. Т.е. сложность данного метода – O(n).
Cложность по памяти
int findIndexByValue (int [] numbers, int value) {
int result = -1;
for(int i = 0; i < numbers.length; i++) {
if(numbers[i] == value) {
result = i;
}
}
return result;
}В данном случае – сложность по памяти – O(1), так как мы используем 1 новую переменную.
List<Integer> findAllNumbersGreater (List<Integer> numbers, int value) {
List<Integer> result = new ArrayList<>();
for(int i = 0; i< numbers.size(); i++) {
if(numbers.get(i) > value) {
result.add(numbers.get(i));
}
}
return result;
}В данном случае, сложность по памяти – O(n), так как мы выделяем место в памяти под новую коллекцию. И, если в ней все числа больше указанного значения, то все элементы переданной коллекции попадут в созданную.
Вывод:
Анализ сложности алгоритмов крайне прост при должной тренировке и не требует глубоких знаний в математике. При этом, он крайне эффективно позволяет определять сложность того или иного метода.