Пошаговое руководство по нотации Big-O
Введение в структуру данных:
В нашей повседневной жизни мы всегда сталкиваемся с различными сценариями, когда организованные вещи облегчают нашу жизнь. Например, в случае с изображением А ниже выбор платья, безусловно, займет меньше времени, чем поиск платья в захламленном шкафу, как на рисунке Б.
Это же правило действует и в мире программирования. Структура данных – это способ организации данных в памяти вашего компьютера, чтобы упростить их обработку и доступ к ним.
Введение в алгоритмы:
Чтобы принести красное платье из шкафа Pic A, в общем, каков был бы процесс, которому кто-то будет следовать? i) Идите в комнату ii) Откройте шкаф iii) Найдите красное платье iv) Выберите красное платье. Это не что иное, как набор инструкций, которым нужно следовать, чтобы выполнить задачу — достать из шкафа красное платье. Аналогичным образом и в программировании мы применяем набор инструкций для выполнения или решения данной задачи. Этот набор инструкций не что иное, как алгоритмы.
Типы структуры данных и алгоритмы:
Различные алгоритмы могут быть использованы для решения данной проблемы по-разному. Например: Напишите программу для нахождения суммы первых n натуральных чисел?
Существует N способов решения проблемы, но, как показано на рисунке 3, некоторые подходы становятся более эффективными с точки зрения времени выполнения или занимаемой пропускной способности сети. Поэтому выбор правильного набора структур данных и алгоритмов для программы очень важен.
Введение в нотацию Big-O:
Big-O — это метрика, используемая для описания эффективности алгоритма. Производительность программы измеряется различными ресурсами, потребляемыми кодом в зависимости от требований продукта. Существует 3 различных оси, на основе которых измеряется производительность.
- Временная сложность: сколько времени требуется для запуска вашей программы. Он имеет дело с объемом обработки или количеством операций, которые код должен выполнить для достижения своей цели.
- Пространственная сложность. Сколько памяти или дискового пространства занимает ваша программа. Это как память, необходимая коду для хранения информации во время выполнения, так и дисковое пространство, необходимое коду для постоянного хранения.
- Сложность сети. Сколько данных ваша программа передает по сети. Величина пропускной способности сети, используемая кодом для передачи информации клиенту или другой системе.
Как выбрать эффективный DSA?
Оптимизируйте свой код в соответствии с вашими системными требованиями. Например, является ли это критической по времени системой или критической по пространству системой. И приложение должно занимать меньше места на мобильном телефоне, в этом случае сложность пространства имеет приоритет, тогда как домашняя страница должна быть открыта и запущена за очень короткое время, в этом случае сложность времени имеет приоритет. Надеюсь, теперь вы знакомы с нотацией Big-O и различными метриками, такими как время, пространство, сеть и т. д.
Есть снова 3 различных типа сложности, которые приходят к картине, например:
i) Big O (Большой O): сложность, которая будет меньше или равна наихудшему времени, которое может занять программа.
ii) Большое Ω (Омега): это сложность, которая будет как минимум больше, чем в лучшем случае.
iii)Большой θ (тета): это сложность, которая находится в пределах наихудшего и наилучшего случая.
Давайте сосредоточимся на наиболее широко используемой сложности, то есть на сложности Big O, и в этой статье мы сосредоточимся на сложности времени. Временная сложность Big-O бывает различных типов, таких как:
- O(1): мы можем назвать это большим O из одного или O из одного, что представляет собой постоянную временную сложность, когда для любого заданного ввода время выполнения не изменится. Он останется постоянным независимо от увеличения или уменьшения набора входных данных N. Например: доступ к определенному индексу в массиве всегда требует временной сложности O (1).
int[] array = {1,3,5,7,9};
System.out.println(array[2]); // output: 5 ---> It doesn’t matter whether the array has 10 or 100 indexes, looking up at a specific location (here at index 2), it will take the same amount of time.
2. O(N): Большое O из N или O из N — это линейная временная сложность, при которой временная сложность будет расти прямо пропорционально размеру входных данных. Пример: обход всех элементов заданного массива.
int[] newArray = {1,3,5,7,9,4,2,0};
for(int i =0; i < newArray.lenght; i++){
System.out.println(newArray[i]); // It visits every element in the array, hence it takes linear time, which means if we have N element in the array it will take N number of time. If N increases time taken also increases and the similar way if N decreases time taken by the program as well decreases.
}
3. O(log N):Big O of log N или Log O of N — это логарифмическая временная сложность, где сложность пропорциональна логарифмическому входу. Пример: поиск элемента в отсортированном массиве.
int[] newArray = {1,2,3,4,5,6,7,8};
for(int i =0; i < newArray.lenght; i+3){
System.out.println(newArray[i]); // It visits only certain elements in the array,as we are doing i+3, hence this is one of the example of Logarithimic time complexity.
}
4. O(N²):Временная сложность алгоритма обозначается как Big O of N² или O of N² , производительность которого прямо пропорциональна квадратному размеру входного набора данных (N). Пример: обход каждого индекса в массиве дважды.
int[] newArray = {1,2,3,4,5,6,7,8};
for(int i=0; i < newArray.lenght; i++){
for(int j=0; j< newArray.lenght; j++){
System.out.println(newArray[i]); // Here two loops are there so j loop run once till all elements of the newArray and then again i loop loop through all the elements of newArray. The time taken here becomes the square size of total input.
}
}
}
5. O(2^n):большой O из 2 в степени N илиэкспоненциальная временная сложность — это алгоритм, рост которого удваивается с каждым добавлением к набору входных данных. . Например. Двойная рекурсия в ряду Фибоначи.
public int fibonacci(int N){
if(N==0 || N==1){
return N;
}
return fibonacci(N-1) + fibonacci(N-2); // Here the recursive instantiation will pass over every number from the number to zero.It will do this twice as it checks f(n-1) once and then again f(n-2) until it reaches the base case if statement i.e N becomes either 1 or 0.
}
6. O(N + M):если алгоритм имеет форму «сначала сделайте это, а когда все сделаете, сделайте то», то вы добавляете среду выполнения. Например Перебрать все элементы в массиве A, а затем перебрать элемент в массиве B.
public static void withTwoLoop(int N, int M){
for(i = 0; i< N ; i++){
System.out.println(i);
}
for(j = 0; j< M; j++){
System.out.println(j); // In this program two loops are there. First loop runs N times, once it is done the second loop runs M times. Hence total time taken can be refered as (N+M) time.
}
}
7. O(N * M): если алгоритм имеет вид «делай это каждый раз, когда делаешь это», то время выполнения умножается. Например, вложенный цикл, где для каждой итерации первого цикла второй цикл повторяется до M раз.
public static void withTwoLoop(int N, int M){
for(int i = 0; i< N ; i++){
for(int j = 0; j< M; j++){
System.out.println(i*j);
} // In this program two loops are there. The difference between this and the previous program is here for each i value the j runs M time. As i runs N time, hence the total time complexity will become O(N*M).
}
}
Это различные временные сложности Big-O, о которых мы говорили до сих пор. Взгляните на приведенный ниже рис. 5, чтобы узнать, какие временные сложности быстрее с точки зрения времени.
Правила измерения большой временной сложности программы:
Теперь давайте возьмем программу и применим приведенные выше правила для расчета временной сложности.
Вот как мы можем рассчитать временную сложность любой задачи. Я надеюсь, что это обсуждение расширит ваши знания об основах структуры данных и алгоритмов (DSA), необходимости DSA, различных типах DSA, нотациях Big-O и различных типах сложностей, наконец, вы получите полное представление о временной сложности и о том, как вычислить временная сложность любой задачи.
Спасибо за чтение этого блога. Если вам понравилось, хлопните в ладоши и поделитесь. Если у вас есть какие-либо сомнения или предложения, не стесняйтесь комментировать или отправить мне электронное письмо. Кроме того, не стесняйтесь подписываться на меня в LinkedIn или Twitter.
