Все время, когда мы пишем код, мы должны думать о том, насколько эффективно решение. Потому что в компьютерном программировании мы часто используем разные способы решения одной проблемы. Например, для сортировки элементов мы можем использовать сортировку слиянием, сортировку вставкой, пузырьковую сортировку и так далее. У всех этих алгоритмов есть свои плюсы и минусы. Когда мы думаем о выборе лучшего алгоритма, в игру вступает нотация Big-O.

Эта статья впервые была опубликована на coseries.com. На этом сайте вы найдете еще несколько информативных статей о DSA.

Для решения проблемы программисты всегда стараются выбрать наиболее эффективный алгоритм. Эффективность алгоритма зависит от двух вещей. Один - это временная сложность, а другой - память или пространственная сложность. В настоящее время память очень дешевая. Следовательно, программисты часто об этом не думают. Итак, для повышения эффективности алгоритма временная сложность является главной проблемой. Когда мы сравниваем два алгоритма, чтобы определить лучший, основная проблема, с которой мы сталкиваемся, - это временная сложность. А для измерения временной сложности мы должны знать, что такое нотация Big-O.

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

Компьютерная программа - это просто список шагов инструкций о том, как компьютер должен работать для решения проблемы. Короче говоря, это называется алгоритмом. Здесь обозначение Big-O определяет, насколько быстрым является алгоритм, и позволяет нам сравнивать программу с другими, показывая взаимосвязь между входными данными и шагами для выполнения алгоритмов. Например, если взаимосвязь между входными данными алгоритма и шагами для выполнения алгоритма является линейной, нотация Big-O будет O (n). А для квадратичной зависимости между входными данными и шагами обозначение Big-O будет O (n²).

Давайте посмотрим на два примера ниже:

Пример 1:

public int addAllElements(int n) {
   int total = 0;
   for (int i = 0; i <= n; i++) {
       total += i;
   }
 return total;
  
}

Пример 2:

public int addAllElements2(int n) {
   return n * (n + 1) / 2;
}

Задачи обоих методов одинаковы. Но в первом примере все шаги для решения задачи будут выполнены n раз. Если значение n равно 10, шаги будут выполняться 10 раз, а если значение n равно 10 миллионам, то все шаги будут выполнены 10 миллионов раз. Здесь вход и шаги увеличиваются линейно. В результате скорость роста временной сложности линейна. Итак, здесь обозначение Big-O - это O (n). График эффективности алгоритма, использованного в примере 1, выглядит следующим образом:

Во втором примере шаги выполняются только один раз. Время выполнения не зависит от ввода. Каким бы ни было значение n, шаги будут выполнены только один раз. И это постоянно. Итак, здесь темп роста временной сложности постоянен. И здесь обозначение Big-O - n (1). График эффективности алгоритма второго метода выглядит следующим образом:

Временная сложность для первого примера - O (n), а для второго - O (1). Итак, совершенно очевидно, что второе решение (или шаги, которые необходимо выполнить, или алгоритм) является наиболее эффективным решением.

Для случаев вложенных циклов For Loops скорость роста будет квадратичной. И будет обозначаться O (n²).

Приведем пример:

public int findDuplicates(int[] elements1, int[] elements2){
	   int count = 0;
	   for (int i = 0; i < elements1.length; i++) {
	       for (int j = 0; j < elements2.length; j++) {
	           if (elements1[i] == elements2[j]){
	               count++;
	           }
	       }
	   }
	   return count;
}

Этот метод используется для поиска повторяющихся элементов в двух списках.

Здесь решение использует вложенный цикл. Если каждый из элементов elements1 и elements2 содержит по 100 элементов, то общее время выполнения цикла будет 100 * 100. Если elements1 содержит n элементов, а elements2 содержит n элементов, то цикл будет выполнен n * n или n² раз. Таким образом, временная сложность решения будет O (n²).

График квадратичного роста представлен ниже:

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

Давайте посмотрим на решение:

pubpublic boolean checkItemInList(int[] n, int itemToCheck){
	   for (int i = 0; i < n.length; i++) {
	       if (n[i] == itemToCheck){
	           return true;
	       }
	   }
	   return false;
}

Этот метод используется для проверки того, есть ли он в списке или нет. Приведенное выше решение говорит нам, что обозначение Big-O - это O (n). Это означает, что если мы хотим проверить элемент (itemToCheck) в списке n, в худшем случае нам придется проверять каждый отдельный элемент (используя алгоритм простого поиска). Но когда мы запустим простой алгоритм поиска, мы можем найти элемент в самом начале списка n, возможно, в первом элементе списка сопоставлен itemToCheck. В этом случае приведенное выше решение вернет истину, а остальная часть программы не запустится. Для этого ввода (itemToCheck, вы проверили в приведенном выше решении) нотация Big-O может быть O (1). Это лучший сценарий. Но все время нотация Big-O рассматривает наихудший сценарий, которым является O (n) для решения, приведенного выше.

Обозначение Big-O не предназначено для измерения времени, в течение которого алгоритм будет работать. Потому что время работы алгоритма зависит от многих вещей. Вместо того, чтобы показывать время, он показывает количество операций, которые алгоритм выполнит. И это количество операций говорит программисту, насколько быстр алгоритм, и помогает программисту сравнивать его с другими.