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

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

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

Квадратичная сложность - O(n*n)

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

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

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

Чаще всего квадратичная сложность появляется при вложенных циклах — когда для каждого элемента массива нам нужно дополнительно пройтись по другим элементам массива.

Пример

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

// Время: O(n*n), где n — размер массива nums
// Память: O(1)
using System.Collections.Generic;

public class Solution {
    public bool ContainsDuplicate(List<int> nums) {
        for (int i = 0; i < nums.Count; i++) {
            for (int j = i + 1; j < nums.Count; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

// Время: O(n*n), где n — размер массива nums
// Память: O(1)
#include <vector>

using namespace std;

bool contains_duplicate(const vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
}

// Время: O(n*n), где n — размер массива nums
// Память: O(1)
func contains_duplicate(nums []int) bool {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] == nums[j] {
                return true
            }
        }
    }
    return false
}

// Время: O(n*n), где n — размер массива nums
// Память: O(1)
import java.util.*;

public class Solution {
    public boolean contains_duplicate(List<Integer> nums) {
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums.get(i).equals(nums.get(j))) {
                    return true;
                }
            }
        }
        return false;
    }
}

# Время: O(n*n), где n — размер массива nums
# Память: O(1)
def contains_duplicate(nums: List[int]) -> bool:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

// Время: O(n*n), где n — размер массива nums
// Память: O(1)
export function contains_duplicate(nums) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] === nums[j]) {
                return true;
            }
        }
    }
    return false;
}

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

Почему время O(n*n)

В Big O мы рассматриваем худший случай — когда программа работает дольше всего. Здесь худший случай — отсутствие дубликатов, ведь тогда придётся перебрать все пары чисел в массиве.

Допустим, nums = [1,2,3,4,5,6,7,8,9,10]. Дополнительно добавим счётчик, который считает число исполненных строк кода:

using System;
using System.Collections.Generic;

public class Solution {
    public bool ContainsDuplicate(List<int> nums) {
        // count считает число исполненных строк кода
        int count = 0;
        for (int i = 0; i < nums.Count; i++) {
            count += 1;
            for (int j = i + 1; j < nums.Count; j++) {
                count += 1;
                if (nums[i] == nums[j]) {
                    count += 1;
                    Console.WriteLine("Программа выполнила " + count + " строк кода");
                    return true;
                }
            }
        }
        Console.WriteLine("Программа выполнила " + count + " строк кода");
        return false;
    }
}

#include <vector>
#include <iostream>

using namespace std;

bool contains_duplicate(const vector<int>& nums) {
    // count считает число исполненных строк кода
    int count = 0;
    for (int i = 0; i < nums.size(); i++) {
        count += 1;
        for (int j = i + 1; j < nums.size(); j++) {
            count += 1;
            if (nums[i] == nums[j]) {
                count += 1;
                cout << "Программа выполнила " << count << " строк кода" << endl;
                return true;
            }
        }
    }
    cout << "Программа выполнила " << count << " строк кода" << endl;
    return false;
}

import "fmt"

func contains_duplicate(nums []int) bool {
    // count считает число исполненных строк кода
    count := 0
    for i := 0; i < len(nums); i++ {
        count += 1
        for j := i + 1; j < len(nums); j++ {
            count += 1
            if nums[i] == nums[j] {
                count += 1
                fmt.Println("Программа выполнила", count, "строк кода")
                return true
            }
        }
    }
    fmt.Println("Программа выполнила", count, "строк кода")
    return false
}

import java.util.*;

public class Solution {
    public boolean contains_duplicate(List<Integer> nums) {
        // count считает число исполненных строк кода
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            count += 1;
            for (int j = i + 1; j < nums.size(); j++) {
                count += 1;
                if (nums.get(i).equals(nums.get(j))) {
                    count += 1;
                    System.out.println("Программа выполнила " + count + " строк кода");
                    return true;
                }
            }
        }
        System.out.println("Программа выполнила " + count + " строк кода");
        return false;
    }
}

def contains_duplicate(nums: List[int]) -> bool:
    # count считает число исполненных строк кода
    count = 0
    for i in range(len(nums)):
        count += 1
        for j in range(i + 1, len(nums)):
            count += 1
            if nums[i] == nums[j]:
                count += 1
                print("Программа выполнила ", count, " строк кода")
                return True
    print("Программа выполнила ", count, " строк кода")
    return False

export function contains_duplicate(nums) {
    // count считает число исполненных строк кода
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        count += 1;
        for (let j = i + 1; j < nums.length; j++) {
            count += 1;
            if (nums[i] === nums[j]) {
                count += 1;
                console.log("Программа выполнила", count, "строк кода");
                return true;
            }
        }
    }
    console.log("Программа выполнила", count, "строк кода");
    return false;
}

Получим 55 исполняемых строк. А теперь давай еще увеличим размер nums.

Размер массива `nums`	Число выполняемых строк
10	55
100	5050
1 000	500500
10 000	50005000
100 000	5000050000
1 000 000	Много…

Самое главное, что при увеличении массива всего в 10 раз число исполняемых строк увеличивается почти в 100 раз! Это и есть признак квадратичный сложности!

Точная формула для количества операций – n*(n+1)/2 . Если раскрыть скобки, получается: (n*n)/2+n/2

В Big O константы и младшие члены отбрасывают, поэтому из (n*n)/2+n/2 остаётся только O(n*n).

P.S. под константой подразумевается n/2. 2 - это константа, которую можно отбросить, потому что она почти никак не влияет на асимптотику и очень мала по сравнению с n*n.

Со временем ты научишься легко определять, какие части формулы можно опустить в Big O. Если что-то пока не до конца ясно — не переживай! Этому мы посвятим отдельный урок!

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

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

Что дальше

Скорее переходи к следующему уроку, чтобы закрепить моменты, которые мы проговаривали ранее только вскользь, чтобы вывести оценку сложности алгоритма на полностью осознанный уровень!