1주차 : 복잡도(Complexity)와 Big-O notation

❓ 복잡도란? 

• 알고리즘의 효율성(성능) 측정을 위한 수단
• 크게 시간 복잡도(알고리즘 실행 시 걸리는 시간)와 공간 복잡도(실행 시 소모하는 메모리의 양)로 나뉨
• 알고리즘의 복잡도는 주로 점근 표기법인 Big-O notation를 사용해 표현한다.

 

1️⃣ 시간 복잡도

• 기준 : input size에 대해 알고리즘이 실행되는 데 걸리는 시간
• 주요 로직의 반복 횟수에 중점
• 주로 사용됨

❕ 계산 예시

    public static int sum(int[] arr, int n) {
        int sum = 0; 
        for (int i = 0; i < n; i++) {
            sum += arr[i];
        }
        return sum;
    }

위와 같은 코드가 있다고 하자. 실행횟수는 다음과 같을 것이다.

코드	실행 횟수
public static int sum(int[] arr, int n) {
int sum = 0;	1
for (int i = 0; i < n; i++) {	n+1
sum += arr[i]; }	n
return sum;	1

 

총 실행 횟수 = 2n + 3 이지만 후술할 Big-O 표기법에 따르면 의미가 없는 상수는 제외되는데, 그렇게 됐을 때 시간 복잡도는 O(n)으로 표기된다.

2️⃣공간 복잡도

• 기준 : 알고리즘을 실행할 때 필요로 하는 자원 공간(메모리)의 양
• 메모리의 발전으로 중요도가 낮아짐

int[] a = new int[1004];

여기서 a 배열은 1004 X 4 byte의 크기를 가지고, 이런 공간(메모리)를 의미함.

 

🅾 Big-O notation(빅오 표기법)

✅ 점근 표기법
worst-case : 최악 입력 & 필요 연산 최대 | Big-O notation (상한선 기준)
best-case : 최적 입력 &필요 연산 최소 | Big-Ω notation
average-case : 총 연산 수 / 시행 회수 | Big-Θ notation

 

• 알고리즘의 성능을 수학적으로 표기해주는 표기법.
• 그래프의 상한선에 가까울수록 성능이 나쁘며, 최악의 경우(worst-case)를 경우하는 표기법.
• 사용 이유 : 점근 표기법 중 가장 이상적인 것은 평균을 나타내는 Big-Θ notation 이나, 이는 도출하기 어렵기 때문에 가장 유사한 성능을 보이는 worst-case의 Big-O notation을 사용한다.
• 목표 : Data나 사용자의 증가율에 따른 알고리즘의 성능 예측
• 규칙
  • 계수 무시 

O(2N + 3) > O(N)

• • 낮은 항 무시

O(2N²+ 3N) > O(N²)

출처: http://bigocheatsheet.com/

 

순위	표기법	명칭	설명
1	O(1)	상수 시간	입력과 상관 없이 일정한 시간이 걸림
2	O(log n)	로그 시간	입력에 대해 로그 시간만큼 연산이 증가
3	O(N)	선형 시간	입력에 비례해 연산이 증가
4	O(NlogN)	로그 선형 시간	입력에 로그를 곱한 만큼 시간이 걸림
5	O(N²)	이차 시간	입력의 제곱에 비례해 연산이 증가
6	O(N³)	삼차 시간	입력의 세제곱에 비례해 연산이 증가
7	O(2ᴺ)	지수 시간	입력에 대해 지수적으로 연산이 증가

 

 위 차트와 표를 참고하면 표기법에 따라 성능을 파악할 수 있다.

시간 복잡도 예제를 통해 표기 법 중 몇가지를 구체적으로 살펴보자.

 

상수 시간 :  O(1)

//입력 크기에 상관없이 항상 동일한 시간이 소요됨. 
// 실행 단계가 하나만 필요하므로 O(1)
public class Main {
    public static int firstElement(int[] array) {
            return array[0];
            }


    public static void main(String[] args) {
        int[] score = {1, 2, 3, 4, 5};
        System.out.println(firstElement(score)); 
    }
}

로그(대수) 시간 :  O(log N)

// 선형 시간과 비슷하지만 런타임은 입력 크기의 절반에 따라 달라짐 
// 즉, 각 반복에서 입력 크기가 감소하면 로그 시간 복잡도(대수 시간 복잡도)를 가짐.
// 예시 : 이진 탐색 

public class Main {
    public static void main(String[] args) {
        int[] score = {12, 22, 45, 67, 96};
        System.out.println(binarySearch(score, 96)); 
    }

    public static int binarySearch(int[] array, int target) {
        int firstIndex = 0;
        int lastIndex = array.length - 1;

        while (firstIndex <= lastIndex) {
            int middleIndex = (firstIndex + lastIndex) / 2;

            if (array[middleIndex] == target) {
                return middleIndex;
            }

            if (array[middleIndex] > target) {
                lastIndex = middleIndex - 1;
            } else {
                firstIndex = middleIndex + 1;
            }
        }
        return -1; 
    }
}

선형 시간 :  O(N)

// 입력 크기에 따라 실행 시간이 선형적으로 증가
// 입력 크기 n에 대해 반복할 때
// 시간 복잡도 O(N)

public class Main {
    public static void main(String[] args) {
        System.out.println(calcFactorial(5)); 
    }

    public static int calcFactorial(int n) {
        int factorial = 1;
        for (int i = 2; i <= n; i++) {
            factorial *= i; // factorial = factorial * i
        }
        return factorial;
    }
}

2차 시간 :  O( N² )

// 중첩 반복일 때

public class Main {
    public static void main(String[] args) {
        int[] array = {12, 34, 45, 12, 56};
        System.out.println(matchElements(array)); 
    }

    public static String matchElements(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                if (i != j && array[i] == array[j]) {
                    return "Match found at " + i + " and " + j;
                }
            }
        }
        return "No matches found";
    }
}

 

지수 시간 :  O( 2ᴺ )

// 피보나치 수열(각 숫자가 앞의 두 숫자의 합)
// 재귀적으로 계산

public class Main {
    public static void main(String[] args) {
        int n = 10; // 10번째 피보나치 수를 계산
        System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));
    }

    public static int fibonacci(int n) {
        // 기본 조건: 첫 번째와 두 번째 피보나치 수는 1
        if (n <= 1) {
            return n;
        }
        // 재귀 호출
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

 

호출 원리

: 각 호출에서 n-1과 n-2가 다시 계산하므로, 트리 구조가 된다.

n=4인 경우 호출 트리는 아래와 같다. 따라서 복잡도는 O(2ᴺ).

fibonacci(4)
├── fibonacci(3)
│   ├── fibonacci(2)
│   │   ├── fibonacci(1) -> 1
│   │   └── fibonacci(0) -> 0
│   └── fibonacci(1) -> 1
└── fibonacci(2)
    ├── fibonacci(1) -> 1
    └── fibonacci(0) -> 0

 

✅ 참고자료 

 

[1] 면접을 위한 CS 전공지식 노트

[2]Big O Cheat Sheet – Time Complexity Chart :

https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/

[3] 시간 복잡도, 공간 복잡도 : https://servertrix.com/880

[4] 빅오 표기법이란 : https://noahlogs.tistory.com/27

[5]How to calculate Big O notation time complexity :

https://blog.stackademic.com/how-to-calculate-big-o-notation-time-complexity-5504bed8d292
[6] 빅오 표기법(Big-O Notation), 시간 복잡도, 공간 복잡도 : https://cjh5414.github.io/big-o-notation/#google_vignette

 

 

 

 

 

 

?

공간 복잡도 - Big-O 표기법