В этом уроке ты
- Научишься оценивать программы асимптотической сложности:
O(1)O(n) - Узнаешь, как применять Big O на практике.
- Закрепишь знания, пройдя тест.
Оценка сложности
Оценка сложности — это способ понять, как долго будет работать программа и сколько памяти она будет потреблять в зависимости от размера входных данных.
Оценку сложности алгоритмов также могут называть асимптотической сложностью. Это одно и то же!
Благодаря оценке сложности можно даже без запуска программы понять, как много ресурсов, в зависимости от входных данных, потребляет программа.
Big O нотация
Big O показывает верхнюю границу сложности алгоритма — то есть максимально возможное потребление ресурсов. Обычно в Big O оценивают время и память. Примеры Big O оценки: O(1), O(n), O(n*n) и т.д.
Big O — это промышленный стандарт. Когда на собеседовании или в работе просят оценить сложность алгоритма, обычно имеют в виду именно Big O. На алгоритмическом собеседовании без оценки алгоритма в Big O нотации зачастую кандидату даже не дают написать код. В общем, это база!
Оцениваем программу в Big O
Теперь посмотрим на несколько программ с популярными оценками в Big O. Твоя задача — взглянуть на примеры и разобраться, почему у них именно такая асимптотическая оценка.
Дальше по курсу мы подробно разберем каждую из оценок сложности. А пока попробуй интуитивно понять почему такая оценка сложности.
Программа 1
// Время: O(1)
// Память: O(1)
public class Solution {
public bool IsZero(List<int> nums, int i) {
bool result = false;
if (nums[i] == 0) {
result = true;
}
return result;
}
}// Время: O(1)
// Память: O(1)
#include <vector>
using namespace std;
bool is_zero(const vector<int>& nums, int i) {
bool result = false;
if (nums[i] == 0) {
result = true;
}
return result;
}// Время: O(1)
// Память: O(1)
func is_zero(nums []int, i int) bool {
result := false
if nums[i] == 0 {
result = true
}
return result
}// Время: O(1)
// Память: O(1)
import java.util.*;
public class Solution {
public boolean is_zero(List<Integer> nums, int i) {
boolean result = false;
if (nums.get(i) == 0) {
result = true;
}
return result;
}
}# Время: O(1)
# Память: O(1)
def is_zero(nums: List[int], i: int) -> bool:
result = False
if nums[i] == 0:
result = True
return result// Время: O(1)
// Память: O(1)
export function is_zero(nums, i) {
let result = false;
if (nums[i] === 0) {
result = true;
}
return result;
}Функция is_zero всегда выполняет одно и то же количество операций и использует одно и то же количество памяти — независимо от того, насколько большой массив nums и какое значение i. Это и есть признак константной сложности: O(1).
Программа 2
// Время: O(n), где n - размер массива nums
// Память: O(n), где n - размер массива nums
// Если nums=[1,2,3,4], то результат [4,3,2,1]
// Если nums=[1,2,3,4,5], то результат [5,4,3,2,1]
public class Solution {
public List<int> ReverseNums(List<int> nums) {
List<int> result = new List<int>();
for (int i = nums.Count - 1; i >= 0; i--) {
result.Add(nums[i]);
}
return result;
}
}// Время: O(n), где n - размер массива nums
// Память: O(n), где n - размер массива nums
// Если nums=[1,2,3,4], то результат [4,3,2,1]
// Если nums=[1,2,3,4,5], то результат [5,4,3,2,1]
#include <vector>
using namespace std;
vector<int> reverse_nums(const vector<int>& nums) {
vector<int> result;
for (int i = nums.size() - 1; i >= 0; i--) {
result.push_back(nums[i]);
}
return result;
}// Время: O(n), где n - размер массива nums
// Память: O(n), где n - размер массива nums
// Если nums=[1,2,3,4], то результат [4,3,2,1]
// Если nums=[1,2,3,4,5], то результат [5,4,3,2,1]
func reverse_nums(nums []int) []int {
result := []int{}
for i := len(nums) - 1; i >= 0; i-- {
result = append(result, nums[i])
}
return result
}// Время: O(n), где n - размер массива nums
// Память: O(n), где n - размер массива nums
// Если nums=[1,2,3,4], то результат [4,3,2,1]
// Если nums=[1,2,3,4,5], то результат [5,4,3,2,1]
import java.util.*;
public class Solution {
public List<Integer> reverse_nums(List<Integer> nums) {
List<Integer> result = new ArrayList<>();
for (int i = nums.size() - 1; i >= 0; i--) {
result.add(nums.get(i));
}
return result;
}
}# Время: O(n), где n - размер массива nums
# Память: O(n), где n - размер массива nums
# Если nums=[1,2,3,4], то результат [4,3,2,1]
# Если nums=[1,2,3,4,5], то результат [5,4,3,2,1]
def reverse_nums(nums: List[int]) -> List[int]:
result = []
for i in range(len(nums) - 1, -1, -1):
result.append(nums[i])
return result// Время: O(n), где n - размер массива nums
// Память: O(n), где n - размер массива nums
// Если nums=[1,2,3,4], то результат [4,3,2,1]
// Если nums=[1,2,3,4,5], то результат [5,4,3,2,1]
export function reverse_nums(nums) {
const result = [];
for (let i = nums.length - 1; i >= 0; i--) {
result.push(nums[i]);
}
return result;
}- Время:
O(n)nums - Память:
O(n)resultnums
Программа 3
// Время: O(n), где n — размер массива nums
// Память: O(1)
// Если nums=[1,2,3,4], результат будет [4,3,2,1]
// Если nums=[1,2,3,4,5], результат будет [5,4,3,2,1]
public class Solution {
public static List<int> ReverseNums(List<int> nums) {
int p1 = 0;
int p2 = nums.Count - 1;
while (p1 < p2) {
int temp = nums[p1];
nums[p1] = nums[p2];
nums[p2] = temp;
p1 += 1;
p2 -= 1;
}
return nums;
}
}// Время: O(n), где n — размер массива nums
// Память: O(1)
// Если nums=[1,2,3,4], результат будет [4,3,2,1]
// Если nums=[1,2,3,4,5], результат будет [5,4,3,2,1]
#include <vector>
using namespace std;
vector<int> reverse_nums(vector<int>& nums) {
int p1 = 0;
int p2 = nums.size() - 1;
while (p1 < p2) {
swap(nums[p1], nums[p2]);
p1 += 1;
p2 -= 1;
}
return nums;
}// Время: O(n), где n — размер массива nums
// Память: O(1)
// Если nums=[1,2,3,4], результат будет [4,3,2,1]
// Если nums=[1,2,3,4,5], результат будет [5,4,3,2,1]
func reverse_nums(nums []int) []int {
p1 := 0
p2 := len(nums) - 1
for p1 < p2 {
nums[p1], nums[p2] = nums[p2], nums[p1]
p1 += 1
p2 -= 1
}
return nums
}// Время: O(n), где n — размер массива nums
// Память: O(1)
// Если nums=[1,2,3,4], результат будет [4,3,2,1]
// Если nums=[1,2,3,4,5], результат будет [5,4,3,2,1]
import java.util.*;
public class Solution {
public List<Integer> reverse_nums(List<Integer> nums) {
int p1 = 0;
int p2 = nums.size() - 1;
while (p1 < p2) {
int temp = nums.get(p1);
nums.set(p1, nums.get(p2));
nums.set(p2, temp);
p1 += 1;
p2 -= 1;
}
return nums;
}
}# Время: O(n), где n — размер массива nums
# Память: O(1)
# Если nums=[1,2,3,4], результат будет [4,3,2,1]
# Если nums=[1,2,3,4,5], результат будет [5,4,3,2,1]
def reverse_nums(nums: List[int]) -> List[int]:
p1 = 0
p2 = len(nums) - 1
while p1 < p2:
nums[p1], nums[p2] = nums[p2], nums[p1]
p1 += 1
p2 -= 1
return nums// Время: O(n), где n — размер массива nums
// Память: O(1)
// Если nums=[1,2,3,4], результат будет [4,3,2,1]
// Если nums=[1,2,3,4,5], результат будет [5,4,3,2,1]
export function reverse_nums(nums) {
let p1 = 0;
let p2 = nums.length - 1;
while (p1 < p2) {
[nums[p1], nums[p2]] = [nums[p2], nums[p1]];
p1 += 1;
p2 -= 1;
}
return nums;
}В этом случае мы не создаём новый массив, поэтому память O(1)O(n)
Про основную задачу Big O
Big O нотацию чаще всего используют, чтобы сравнить несколько решений одной задачи, а не чтобы померить конкретное время работы. Big O лишь косвенно связано с фактическим временем исполнения. Из-за этого и возникают распространённые заблуждения.
Главная задача Big O — показать, как изменятся затраты по времени и памяти, если увеличить объем данных в 10, 100 или 1000 раз и более. Big O не предназначена для точного измерения времени исполнения.
Что дальше
Переходи к следующему уроку, чтобы узнать о хитрых случаях оценки Big O и ещё больше прокачать навыки анализа кода!