Базовая оценка сложности

• Начнешь изучать оценку сложности
• Узнаешь, как можно тестировать решение на скорость
• Измеришь скорость программы

Представь, что ты разрабатываешь программу, которой одновременно пользуются миллионы человек. Это очень много, и даже одна ошибка может стоить компании огромных потерь! Тебе предстоит просматривать код своих коллег-разработчиков и решать, можно ли использовать их решения в важном сервисе. На тебе лежит большая ответственность, но я буду тебе помогать и уверен, что у тебя все получится!

Допустим, в одной из частей программы твоему коллеге нужно проверить, есть ли дубликаты в массиве, и тебе поручили проверить его код. Ниже приведены примеры ожидаемого поведения программы.

Ввод: nums = [1,4,2,5,8]
Вывод: false
Объяснение: в массиве nums каждое число встречается один раз, поэтому вернули false

Ввод: nums = [5,3,0,2,3]
Вывод: true
Объяснение: в массиве nums тройка встречается 2 раза, поэтому ответ true

Коллега решил перебрать все пары чисел. Как только встречается пара одинаковых чисел, программа останавливается и возвращает true. Если одинаковых чисел нет, после полного перебора возвращается false. Решение точно работает верно, но вот оптимально ли?

class Solution {
    static 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;
    }
}

#include <iostream>
#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;
}

package main

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
}

import java.util.*;

public class Solution {
    static 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;
    }
}

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

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;
}

Чтобы проверить, насколько оптимально решение, ты запустил его с разными размерами массива nums и замерил время выполнения:

Главное, что можно заметить: программа начинает долго работать уже при 10 000 элементах. Сегодня большинство сервисов стремятся, чтобы их операции укладывались примерно в 150 миллисекунд, а тут уже приходится ждать целых 2 секунды…

Программа работает довольно быстро, если массив небольшой, но при большом размере массива ждать приходится очень долго. В высоконагруженном сервисе могут встречаться длинные массивы, поэтому такое решение точно не подходит. Нужно искать другой способ!

Но как все успеть? Ведь только на запуск этого небольшого куска кода у тебя ушло так много времени! А впереди еще много коллег, которым нужна твоя помощь!

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