Массивы и O(n)

В этом уроке ты

Освоишь оценку сложности O(n) на примерах
Научишься распознавать линейную сложность по времени и памяти
Научишься оценивать время и память при работе с 2D массивами

Линейная сложность

Алгоритм имеет линейную сложность, если время его выполнения пропорционально размеру входных данных. Обозначается как O(n).

Другими словами, если размер входных данных увеличится в 100 раз, то время и/или память алгоритма тоже вырастут примерно в 100 раз.

Когда встречается

- Линейная временная сложность чаще всего возникает, когда мы в цикле проходим по всему массиву.

- Линейная память обычно появляется, когда мы создаём дополнительный массив того же размера, что и исходный.

// Время: 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]
using System.Collections.Generic;

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), потому что мы создаём новый массив result такого же размера, как nums.

Бонус: 2D массивы

// Время: O(n*m), где n - число строк, m - число столбцов
// Память: O(1)

public class Solution {
    public void PrintMatrix(List<List<int>> mat) {
        for (int i = 0; i < mat.Count; i++) {
            for (int j = 0; j < mat[i].Count; j++) {
                Console.WriteLine(mat[i][j]);
            }
        }
    }
}

// Время: O(n*m), где n - число строк, m - число столбцов
// Память: O(1)
#include <vector>
#include <iostream>

using namespace std;

void print_matrix(const vector<vector<int>>& mat) {
    for (int i = 0; i < mat.size(); i++) {
        for (int j = 0; j < mat[i].size(); j++) {
            cout << mat[i][j] << endl;
        }
    }
}

// Время: O(n*m), где n - число строк, m - число столбцов
// Память: O(1)
import "fmt"

func print_matrix(mat [][]int) {
    for i := 0; i < len(mat); i++ {
        for j := 0; j < len(mat[i]); j++ {
            fmt.Println(mat[i][j])
        }
    }
}

// Время: O(n*m), где n - число строк, m - число столбцов
// Память: O(1)
import java.util.*;

public class Solution {
    public void print_matrix(List<List<Integer>> mat) {
        for (int i = 0; i < mat.size(); i++) {
            for (int j = 0; j < mat.get(i).size(); j++) {
                System.out.println(mat.get(i).get(j));
            }
        }
    }
}

# Время: O(n*m), где n - число строк, m - число столбцов
# Память: O(1)
def print_matrix(mat: List[List[int]]) -> None:
    for i in range(len(mat)):
        for j in range(len(mat[i])):
            print(mat[i][j])

// Время: O(n*m), где n - число строк, m - число столбцов
// Память: O(1)
export function print_matrix(mat) {
    for (let i = 0; i < mat.length; i++) {
        for (let j = 0; j < mat[i].length; j++) {
            console.log(mat[i][j]);
        }
    }
}

При работе с двумерными массивами сложность часто оценивают исходя из общего числа элементов, которая вычисляется как n*m, где n — число строк, а m — число столбцов. При обходе всех элементов 2D-массива получаем оценку по времени O(n*m).

Сложность можно также записать как O(n), если n обозначает общее число элементов в массиве. Однако O(n*m) более предпочтительно, так как оно явно указывает на зависимость от числа строк и столбцов.

Самые частые оценки при работе с двумерными массивами это: O(n*m), O(n), O(m), O(1).

Главные выводы

Если оценка кода по времени и памяти O(n) это значит, что при увеличении размера входных данных в 100 раз алгоритм увеличит потребляемую память и время исполнение примерно в 100 раз.
При обходе двумерного массива сложность по времени оценивается как O(n*m).
Линейная сложность – самая популярная асимптотическая оценка.

Что дальше

Скорее переходи к изучению оценки сложности O(n*n), чтобы вовремя избежать неоптимальных алгоритмов.