Погружение в O(1)

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

Узнаешь, почему функция с оценкой O(1) может работать хоть 100 секунд
Освоишь оценку сложности O(1) на примерах

Константная сложность - O(1)

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

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

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

Чаще всего константная сложность возникает в базовых арифметических и логических операциях.

Примеры

	Пример в коде	Оценка по времени	Оценка по памяти
Создание переменной	`int a`	O(1)	O(1)
Арифметические операции (`+`, `-`, `*`, `/`, `%`, …)	`c = a + b`	O(1)	O(1)
Логические операции(`&&`, `\|\|`, `and`, `or`, `not`, …)	`if a == b and …`	O(1)	O(1)
Создание массива фиксированной длины (длина не меняется!)	`int[26] arr;`	O(1)	O(1)
Доступ по индексу в массиве	`x = arr[12]`	O(1)	O(1)
Любые другие операции, которые всегда занимают одинаковое время…	…	O(1)	O(1)

Такое разное O(1)

Ниже два примера программ, у которых и время, и память оцениваются как O(1):

// Время: O(1)
// Память: O(1)
public class Solution {
    static int x = 3;
    static int y = x * 2;

    static Solution() {
        x = x + y;
        Console.WriteLine(x);
    }
}

// Время: O(1)
// Память: O(1)
#include <iostream>

using namespace std;

int x = 3;
int y = x * 2;

__attribute__((constructor)) void run() {
    x = x + y;
    cout << x << endl;
}

// Время: O(1)
// Память: O(1)
package main

import "fmt"

var x = 3
var y = x * 2

func init() {
    x = x + y
    fmt.Println(x)
}

// Время: O(1)
// Память: O(1)
import java.util.*;

public class Solution {
    static int x = 3;
    static int y = x * 2;

    static {
        x = x + y;
        System.out.println(x);
    }
}

# Время: O(1)
# Память: O(1)
x = 3
y = x * 2
x = x + y
print(x)

// Время: O(1)
// Память: O(1)
export function run() {
    let x = 3;
    let y = x * 2;
    x = x + y;
    console.log(x);
}

Время выполнения: ~0.0001 секунды

// Время: O(1)
// Память: O(1)
using System;

public class Solution {
    static Solution() {
        long result = 0;
        for (int i = 0; i < 100_000_000; i++) {
            result += i;
        }
        Console.WriteLine(result);
    }
}

// Время: O(1)
// Память: O(1)
#include <iostream>
using namespace std;

__attribute__((constructor)) void run() {
    long long result = 0;
    for (int i = 0; i < 100000000; i++) {
        result += i;
    }
    cout << result << endl;
}

// Время: O(1)
// Память: O(1)
package main

import "fmt"

func init() {
    var result int64 = 0
    for i := 0; i < 100000000; i++ {
        result += int64(i)
    }
    fmt.Println(result)
}

// Время: O(1)
// Память: O(1)
import java.util.*;

public class Solution {
    static {
        long result = 0;
        for (int i = 0; i < 100_000_000; i++) {
            result += i;
        }
        System.out.println(result);
    }
}

# Время: O(1)
# Память: O(1)
result = 0
for i in range(100_000_000):
    result += i
print(result)

// Время: O(1)
// Память: O(1)
export function run() {
    let result = 0;
    for (let i = 0; i < 100_000_000; i++) {
        result += i;
    }
    console.log(result);
}

Время выполнения: ~6 секунд

Обе программы имеют оценку O(1) по времени и памяти, однако разница в реальном времени исполнения колоссальна!

Если программа работает за O(1), это совсем не значит, что она работает молниеносно. Это означает, что время выполнения не зависит от размера входных данных и остаётся постоянным (пусть даже это будет 6 секунд, 100 секунд и так далее).

Когда заканчивается O(1)

// Время: O(1)
// Память: O(1)
using System;

public class Solution {
    static Solution() {
        long result = 0;
        for (int i = 0; i < 100_000_000; i++) {
            result += i;
        }
        Console.WriteLine(result);
    }
}

// Время: O(1)
// Память: O(1)
#include <iostream>

using namespace std;

__attribute__((constructor)) void run() {
    long long result = 0;
    for (int i = 0; i < 100000000; i++) {
        result += i;
    }
    cout << result << endl;
}

// Время: O(1)
// Память: O(1)
package main

import "fmt"

func init() {
    var result int64 = 0
    for i := 0; i < 100_000_000; i++ {
        result += int64(i)
    }
    fmt.Println(result)
}

// Время: O(1)
// Память: O(1)
import java.util.*;

public class Solution {
    static {
        long result = 0;
        for (int i = 0; i < 100_000_000; i++) {
            result += i;
        }
        System.out.println(result);
    }
}

# Время: O(1)
# Память: O(1)
result = 0
for i in range(100_000_000):
    result += i
print(result)

// Время: O(1)
// Память: O(1)
export function run() {
    let result = 0;
    for (let i = 0; i < 100_000_000; i++) {
        result += i;
    }
    console.log(result);
}

В этом примере цикл выполняется 100 миллионов раз. Кажется, что есть «магическое» число итераций, после которого нельзя считать программу работающей за O(1). Но такого числа нет. Если в коде есть некая неизменная константа (хоть 10^9, хоть 10^100), то это всё равно O(1).

Одна строка в коде ≠ O(1)

Какова временная и пространственная сложность кода, который возвращает true, если массив nums содержит два числа, в сумме дающих target?

public class Solution {
    public bool TwoSum(List<int> nums, int target) {
        List<int> used = new List<int>();
        foreach (int num in nums) {
            int second_num = target - num;
            // Операция поиска по списку
            if (used.Contains(second_num)) {
                return true;
            }
            used.Add(num);
        }
        return false;
    }
}

#include <vector>

using namespace std;

bool two_sum(const vector<int>& nums, int target) {
    vector<int> used;
    for (int num : nums) {
        int second_num = target - num;
        // Операция поиска по списку
        for (int x : used) {
            if (x == second_num) {
                return true;
            }
        }
        used.push_back(num);
    }
    return false;
}

func two_sum(nums []int, target int) bool {
    used := []int{}
    for _, num := range nums {
        second_num := target - num
        // Операция поиска по списку
        for _, x := range used {
            if x == second_num {
                return true
            }
        }
        used = append(used, num)
    }
    return false
}

import java.util.*;

public class Solution {
    public boolean two_sum(List<Integer> nums, int target) {
        List<Integer> used = new ArrayList<>();
        for (int num : nums) {
            int second_num = target - num;
            // Операция поиска по списку
            if (used.contains(second_num)) {
                return true;
            }
            used.add(num);
        }
        return false;
    }
}

def two_sum(nums: List[int], target: int) -> List[int]:
    used = []
    for num in nums:
        second_num = target - num
        # Операция поиска по списку
        if second_num in used:
            return True
        used.append(num)
    return False

export function two_sum(nums, target) {
    const used = [];
    for (const num of nums) {
        const second_num = target - num;
        // Операция поиска по списку
        if (used.includes(second_num)) {
            return true;
        }
        used.push(num);
    }
    return false;
}

Память: O(n), где n — размер массива nums. Динамический массив used может вырасти до такого же размера.
Время: O(n*n), поскольку операция поиска по списку занимает O(n) и выполняется внутри цикла по всем элементам.

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

Встроенные в язык функции могут ввести в заблуждение: перед использованием любой функции важно уточнить её временную и пространственную сложность в документации.

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

Если оценка кода O(1) это значит, что при увеличении размера входных данных алгоритм не изменит потребляемую память и время исполнение.
Одна строка в коде ≠ O(1)

Что дальше

Скорее переходи к следующему уроку!