Вступ

Позначення Великої О (Big O notation) — це спосіб вимірювати ефективність алгоритмів з точки зору часу (складність виконання) та простору (складність по пам'яті). Воно зосереджене на тому, як алгоритм масштабуватиметься зі збільшенням розміру вхідних даних, що робить його важливим інструментом для розробників, які створюють масштабовані додатки. Цей посібник розглядає позначення Великої О з повними прикладами коду на Java, очікуваними результатами та детальними поясненнями.

Загальні позначення Великої О з прикладами

1. Стала складність часу: O(1)

Час виконання є сталим, незалежно від розміру вхідних даних.

Приклад коду

public class ConstantTimeExample {  
 public static void main(String[] args) {  
 int[] arr = {10, 20, 30, 40};  
 System.out.println(getFirstElement(arr)); // Вивід: 10  
 }  

 public static int getFirstElement(int[] arr) {  
 return arr[0];  
 }  
}

Вивід:

10

Пояснення: Доступ до першого елемента масиву займає сталий час, O(1).

2. Логарифмічна складність часу: O(log n)

Час виконання збільшується логарифмічно із збільшенням розміру вхідних даних, зазвичай зустрічається в алгоритмах, таких як бінарний пошук.

Приклад коду:

public class LogarithmicTimeExample {  
 public static void main(String[] args) {  
 int[] arr = {1, 3, 5, 7, 9, 11, 13};  
 int target = 7;  
 System.out.println(binarySearch(arr, target)); // Вивід: 3  
 }  

 public static int binarySearch(int[] arr, int target) {  
 int low = 0, high = arr.length - 1;  
 while (low <= high) {  
 int mid = (low + high) / 2;  
 if (arr[mid] == target) return mid;  
 if (arr[mid] < target) low = mid + 1;  
 else high = mid - 1;  
 }  
 return -1;  
 }  
}

Вивід:

3

Пояснення: Масив ділиться на половини, зменшуючи простір пошуку логарифмічно.

3. Лінійна складність часу: O(n)

Час виконання зростає пропорційно до розміру вхідних даних.

Приклад коду:

public class LinearTimeExample {  
 public static void main(String[] args) {  
 int[] arr = {10, 20, 30, 40};  
 System.out.println(findMax(arr)); // Вивід: 40  
 }  

 public static int findMax(int[] arr) {  
 int max = arr[0];  
 for (int num : arr) {  
 if (num > max) max = num;  
 }  
 return max;  
 }  
}

Вивід:

40

Пояснення: Кожен елемент перевіряється один раз, що дає складність O(n).

4. Квадратична складність часу: O(n²)

Час виконання зростає квадратично з розміром вхідних даних, зазвичай через вкладені цикли.

Приклад коду:

public class QuadraticTimeExample {  
 public static void main(String[] args) {  
 int[] arr = {1, 2, 3};  
 printPairs(arr);  
 }  

 public static void printPairs(int[] arr) {  
 for (int i = 0; i < arr.length; i++) {  
 for (int j = i + 1; j < arr.length; j++) {  
 System.out.println("(" + arr[i] + ", " + arr[j] + ")");  
 }  
 }  
 }  
}

Вивід:

(1, 2)  
(1, 3)  
(2, 3)

Пояснення: Вкладений цикл призводить до квадратичної складності O(n²).

5. Експоненціальна складність часу: O(2ⁿ)

Час виконання подвоюється з кожним новим елементом, що часто зустрічається в рекурсивних алгоритмах.

Приклад коду:

public class ExponentialTimeExample {  
 public static void main(String[] args) {  
 int n = 4;  
 System.out.println(fibonacci(n)); // Вивід: 3  
 }  

 public static int fibonacci(int n) {  
 if (n <= 1) return n;  
 return fibonacci(n - 1) + fibonacci(n - 2);  
 }  
}

Вивід:

3

Пояснення: Функція обчислює числа Фібоначчі з надлишковими рекурсивними викликами, що призводить до експоненційної складності.

Приклади складності по пам'яті

1. Стала складність по пам'яті: O(1)

Використання пам'яті є сталим, незалежно від розміру вхідних даних.

Приклад коду:

public class ConstantSpaceExample {  
 public static void main(String[] args) {  
 int[] arr = {10, 20, 30};  
 System.out.println(sumArray(arr)); // Вивід: 60  
 }  

 public static int sumArray(int[] arr) {  
 int sum = 0; // O(1) простір  
 for (int num : arr) {  
 sum += num;  
 }  
 return sum;  
 }  
}

Вивід:

60

## Лінійна складність по пам'яті: O(n)

Використання пам'яті зростає лінійно з розміром вхідних даних.

import java.util.ArrayList;

public class LinearSpaceExample {
public static void main(String[] args) {
int n = 5;
System.out.println(generateList(n)); // Вивід: [1, 2, 3, 4, 5]
}

public static ArrayList generateList(int n) {
ArrayList list = new ArrayList<>();
for (int i = 1; i <= n; i++) {
list.add(i);
}
return list;
}
}
```

Вивід:

[1, 2, 3, 4, 5]

Висновок

Позначення Великої О є важливим для розуміння та оптимізації ефективності алгоритмів. Аналізуючи складності часу та пам'яті, розробники можуть передбачити, як алгоритми поводитимуться при зростанні розміру вхідних даних. Наведені приклади на Java демонструють, як різні складності проявляються в реальних сценаріях, допомагаючи вам розробляти кращі та масштабованіші системи.

Перекладено з: Big O Notation: A Comprehensive Guide to Runtime and Space Complexity in Java