Big O Notation 설명

Source: Dev.to

Introduction

Big O 표기법은 입력 크기가 증가함에 따라 알고리즘의 실행 시간이 어떻게 성장하는지를 설명합니다. 가장 흔한 복잡도를 이해하면 더 빠르고 확장 가능한 코드를 작성하고 성능 문제를 조기에 발견할 수 있습니다.

O(1) – Constant Time

O(1) 알고리즘은 입력 크기에 관계없이 동일한 시간만큼 실행됩니다.

var users = new Dictionary
{
    { 1, "Caique" },
    { 2, "Maria" },
    { 3, "Fernanda" },
};

var user = users[1];   // Dictionary lookup by key is O(1)

O(log n) – Logarithmic Time

로그arithmic 알고리즘은 매 단계마다 문제 크기를 일정 비율(보통 2)로 줄입니다. 대표적인 예가 정렬된 배열에 대한 이진 탐색입니다.

int BinarySearch(int[] array, int target)
{
    int left = 0;
    int right = array.Length - 1;

    while (left  // example truncated in source
}

O(n) – Linear Time

각 요소를 한 번씩 처리하는 단순 루프는 선형 시간에 실행됩니다.

var users = new List { "Caique", "Maria", "Fernanda" };

foreach (var user in users)
{
    Console.WriteLine(user);
}

리스트가 10 % 증가하면 루프가 끝나는 데 걸리는 시간도 대략 10 % 더 오래 걸립니다.

O(n log n) – Linearithmic Time

많은 효율적인 정렬 알고리즘(예: 병합 정렬, 퀵 정렬)은 O(n log n) 시간 복잡도를 가집니다.

var numbers = new List { 5, 2, 8, 1, 3 };
numbers.Sort();   // .Sort() uses an O(n log n) algorithm internally

O(n²) – Quadratic Time

이차 복잡도는 알고리즘에 외부 반복마다 전체 입력을 다시 순회하는 중첩 루프가 포함될 때 발생합니다.

var users = new List { "Caique", "Maria", "Fernanda" };

foreach (var user1 in users)
{
    foreach (var user2 in users)
    {
        Console.WriteLine($"{user1} - {user2}");
    }
}

연산 수가 입력 크기의 제곱에 비례해 증가하므로 성능 병목 현상이 빠르게 나타날 수 있습니다.

Conclusion

프론트엔드든 백엔드든 관계없이 이러한 일반적인 Big O 패턴을 알면 성능 문제가 심각해지기 전에 진단하고 피할 수 있습니다. 기능 요구사항을 충족하면서 가능한 가장 낮은 복잡도를 목표로 하세요.