Линейная vs квадратичная сложность

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

Развеешь миф, что вложенные циклы — это всегда O(n*n).
Научишься определять сложность алгоритма, даже если не понимаешь его логику.

Хитрый пример с O(n)

Рассмотрим следующий код (достаточно просто просмотреть его, но не вникать в смысл):

using System.Collections.Generic;

public class Solution {
    public int LongestOnes(List<int> nums, int k) {
        int l = 0;
        int r = -1;
        int result = 0;
        int zerosCount = 0;

        while (l < nums.Count) {
            while (r + 1 < nums.Count && (nums[r + 1] == 1 || zerosCount < k)) {
                if (nums[r + 1] == 0) {
                    zerosCount += 1;
                }
                r += 1;
            }
            int windowSize = r - l + 1;
            result = System.Math.Max(result, windowSize);
            if (nums[l] == 0) {
                zerosCount -= 1;
            }
            l += 1;
        }
        return result;
    }
}

#include <vector>
#include <algorithm>

using namespace std;

int longest_ones(const vector<int>& nums, int k) {
    int l = 0;
    int r = -1;
    int result = 0;
    int zerosCount = 0;

    while (l < nums.size()) {
        while (r + 1 < nums.size() && (nums[r + 1] == 1 || zerosCount < k)) {
            if (nums[r + 1] == 0) {
                zerosCount += 1;
            }
            r += 1;
        }
        int windowSize = r - l + 1;
        result = max(result, windowSize);
        if (nums[l] == 0) {
            zerosCount -= 1;
        }
        l += 1;
    }
    return result;
}

func longest_ones(nums []int, k int) int {
    l := 0
    r := -1
    result := 0
    zerosCount := 0

    for l < len(nums) {
        for r+1 < len(nums) && (nums[r+1] == 1 || zerosCount < k) {
            if nums[r+1] == 0 {
                zerosCount += 1
            }
            r += 1
        }
        windowSize := r - l + 1
        if windowSize > result {
            result = windowSize
        }
        if nums[l] == 0 {
            zerosCount -= 1
        }
        l += 1
    }
    return result
}

import java.util.*;

public class Solution {
    public int longest_ones(List<Integer> nums, int k) {
        int l = 0;
        int r = -1;
        int result = 0;
        int zerosCount = 0;

        while (l < nums.size()) {
            while (r + 1 < nums.size() && (nums.get(r + 1) == 1 || zerosCount < k)) {
                if (nums.get(r + 1) == 0) {
                    zerosCount += 1;
                }
                r += 1;
            }
            int windowSize = r - l + 1;
            result = Math.max(result, windowSize);
            if (nums.get(l) == 0) {
                zerosCount -= 1;
            }
            l += 1;
        }
        return result;
    }
}

def longest_ones(nums: List[int], k: int) -> int:
    l = 0
    r = -1
    result = 0
    zerosCount = 0

    while l < len(nums):
        while r + 1 < len(nums) and (nums[r + 1] == 1 or zerosCount < k):
            if nums[r + 1] == 0:
                zerosCount += 1
            r += 1
        windowSize = r - l + 1
        result = max(result, windowSize)
        zerosCount += -1 if nums[l] == 0 else 0
        l = l + 1
    return result

export function longest_ones(nums, k) {
    let l = 0;
    let r = -1;
    let result = 0;
    let zerosCount = 0;

    while (l < nums.length) {
        while (r + 1 < nums.length && (nums[r + 1] === 1 || zerosCount < k)) {
            if (nums[r + 1] === 0) {
                zerosCount += 1;
            }
            r += 1;
        }
        const windowSize = r - l + 1;
        result = Math.max(result, windowSize);
        if (nums[l] === 0) {
            zerosCount -= 1;
        }
        l += 1;
    }
    return result;
}

Память: O(1), так как храним лишь несколько переменных.

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

Чтобы оценить код по времени и памяти не обязательно понимать что он делает.

Почему оценка по времени O(n)

Чтобы определить сложность, нужно смотреть на то, как двигаются переменные l и r, потому что они отвечают за условия остановки в цикле:

l в основном цикле while l < len(nums) двигается только вперёд.
r во внутреннем цикле (while r + 1 < len(nums) and (...)) тоже двигается только вперёд.

В худшем случае l может пройти весь массив за n шагов, и r тоже может сделать не более n шагов (где n — размер массива nums). Получаем всего n+n=2n шагов, что сводится к O(n).

Даже если есть вложенный цикл, он не всегда означает O(n*n). Здесь важен факт, что указатели l и r всегда увеличиваются (хотя бы в одной итерации увеличится или l или r) и не откатываются назад, поэтому время работы — O(n).

Как 100% определить O(n)

Воспользуемся простым трюком: создадим переменную count, которая увеличивается после каждой выполненной строки кода. Например:

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestOnes(List<int> nums, int k) {
        int l = 0;
        int r = -1;
        int result = 0;
        int zerosCount = 0;
        int count = 4; // учтём 4 предыдущие строки

        while (l < nums.Count) {
            count += 1;
            while (r + 1 < nums.Count && (nums[r + 1] == 1 || zerosCount < k)) {
                count += 1;

                if (nums[r + 1] == 0) {
                    count += 1;
                    zerosCount += 1;
                    count += 1;
                }
                r += 1;
                count += 1;
            }
            int windowSize = r - l + 1;
            count += 1;

            result = Math.Max(result, windowSize);
            count += 1;

            if (nums[l] == 0) zerosCount -= 1;
            count += 1;

            l += 1;
            count += 1;
        }

        Console.WriteLine("Программа выполнила " + count + " строк кода");
        return result;
    }
}

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int longest_ones(const vector<int>& nums, int k) {
    int l = 0;
    int r = -1;
    int result = 0;
    int zerosCount = 0;
    int count = 4; // учтём 4 предыдущие строки

    while (l < nums.size()) {
        count += 1;
        while (r + 1 < nums.size() && (nums[r + 1] == 1 || zerosCount < k)) {
            count += 1;

            if (nums[r + 1] == 0) {
                count += 1;
                zerosCount += 1;
                count += 1;
            }
            r += 1;
            count += 1;
        }
        int windowSize = r - l + 1;
        count += 1;

        result = max(result, windowSize);
        count += 1;

        if (nums[l] == 0) zerosCount -= 1;
        count += 1;

        l += 1;
        count += 1;
    }

    cout << "Программа выполнила " << count << " строк кода" << endl;
    return result;
}

import "fmt"

func longest_ones(nums []int, k int) int {
    l := 0
    r := -1
    result := 0
    zerosCount := 0
    count := 4 // учтём 4 предыдущие строки

    for l < len(nums) {
        count += 1
        for r+1 < len(nums) && (nums[r+1] == 1 || zerosCount < k) {
            count += 1

            if nums[r+1] == 0 {
                count += 1
                zerosCount += 1
                count += 1
            }
            r += 1
            count += 1
        }
        windowSize := r - l + 1
        count += 1

        if windowSize > result {
            result = windowSize
        }
        count += 1

        if nums[l] == 0 {
            zerosCount -= 1
        }
        count += 1

        l += 1
        count += 1
    }

    fmt.Println("Программа выполнила", count, "строк кода")
    return result
}

import java.util.*;

public class Solution {
    public int longest_ones(List<Integer> nums, int k) {
        int l = 0;
        int r = -1;
        int result = 0;
        int zerosCount = 0;
        int count = 4; // учтём 4 предыдущие строки

        while (l < nums.size()) {
            count += 1;
            while (r + 1 < nums.size() && (nums.get(r + 1) == 1 || zerosCount < k)) {
                count += 1;

                if (nums.get(r + 1) == 0) {
                    count += 1;
                    zerosCount += 1;
                    count += 1;
                }
                r += 1;
                count += 1;
            }
            int windowSize = r - l + 1;
            count += 1;

            result = Math.max(result, windowSize);
            count += 1;

            if (nums.get(l) == 0) {
                zerosCount -= 1;
            }
            count += 1;

            l += 1;
            count += 1;
        }

        System.out.println("Программа выполнила " + count + " строк кода");
        return result;
    }
}

# Время: O(n), где n - размер nums
# Память: O(1)
def longest_ones(nums: List[int], k: int) -> int:
    l = 0
    r = -1
    result = 0
    zerosCount = 0
    # count - число строк кода исполненных
    count = 4 # учтём 4 предыдущие строки

    while l < len(nums):
        count += 1
        while r + 1 < len(nums) and (nums[r + 1] == 1 or zerosCount < k):
            count += 1

            if nums[r + 1] == 0:
                count += 1
                
                zerosCount += 1
                count += 1
            r += 1
            count += 1
        windowSize = r - l + 1
        count += 1
 
        result = max(result, windowSize)
        count += 1
        
        zerosCount += -1 if nums[l] == 0 else 0
        count += 1
        
        l = l + 1
        count += 1
    print("Программа выполнила ", count, " строк кода")
    return result

export function longest_ones(nums, k) {
    let l = 0;
    let r = -1;
    let result = 0;
    let zerosCount = 0;
    let count = 4; // учтём 4 предыдущие строки

    while (l < nums.length) {
        count += 1;
        while (r + 1 < nums.length && (nums[r + 1] === 1 || zerosCount < k)) {
            count += 1;

            if (nums[r + 1] === 0) {
                count += 1;
                zerosCount += 1;
                count += 1;
            }
            r += 1;
            count += 1;
        }
        const windowSize = r - l + 1;
        count += 1;

        result = Math.max(result, windowSize);
        count += 1;

        if (nums[l] === 0) {
            zerosCount -= 1;
        }
        count += 1;

        l += 1;
        count += 1;
    }

    console.log("Программа выполнила", count, "строк кода");
    return result;
}

После запуска кода с разными размерами массива nums получились такие результаты:

Размер массива `nums`	Число выполненных строк кода
10	86
100	816
1000	8002

Заметь, что когда n увеличивается в 10 раз (от 10 до 100 и от 100 до 1000), число строк тоже растёт примерно в 10 раз. Это указывает на линейную зависимость и подтверждает оценку O(n).

Не стоит делать Big O оценку основываясь на время выполнения алгоритма, так как на малых данных могут сработать различные оптимизации. Подсчёт исполняемых строк даёт более наглядную картину.

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

Вложенный цикл — это не всегда O(n*n). В нашем примере видим O(n), потому что указатели двигаются только вперёд.
Если не получается «на глаз» определить сложность, можно посчитать число исполняемых строк кода для разных размеров входных данных.
В коде могут быть аргументы, не влияющие на итоговую оценку (как k в примере).