[DSA] Complexity

복잡도

Time Complexity: This tells us how much time our code takes to run.
Space Complexity: This tells us how much memory our code uses

 

시간 복잡도는 코드 실행시간을 알려주고, 공간 복잡도는 코드가 사용하는 메모리양을 알려준다.

 

 

자주 쓰이는 복잡도

함수	명칭	예
1	상수형	연결리스트 맨 앞 항목 추가하기
logn	로그형	정렬된 배열에서 항목 찾기
n	선형	정렬되지 않은 배열에서 항목 찾기
nlogn	선형로그형	n개의 항목을 분할 정복 방식으로 병합 정렬하기
n²	2차형	그래프에서 두 개의 정점 간의 최단 거리 구하기
n³	3차형	행렬 계산하기
2ⁿ	지수형	하노이 탑 문제

 

알고리즘 분석

최악

• 알고리즘이 오래 걸리는 경우
• 알고리즘이 느리게 수행되는 것을 입력으로 설정

최선

• 알고리즘이 제일 적은 시간이 걸리는 경우
• 알고리즘이 가장 빨리 수행되는 것을 입력으로 설정

평균

• 알고리즘의 예상 수행 시간 제시
• 입력이 무작위(하한 시간 ≤ 평균시간 ≤ 상한시간)

 

 

 

점근 표기법

 

빅 오 표기법(Big O)

• 주어진 함수에 대해 엄밀한(tight) 상한을 찾게 해준다.
• 최악을 가정하고, 코드 분석에 가장 일반적으로 사용되는 표기
• 실행 시간이나 메모리 사용량에 대한 상한을 제공(상한과 하한이 같을 경우 세타 표기법 사용)

 

상수 시간 복잡도 O(1): 상수 루프, 배열 접근

 

- 함수(또는 명령문 집합)의 시간 복잡도는 루프, 재귀 및 기타 비상수 시간 함수 호출을 포함하지 않는 경우 O(1)로 간주

- 알고리즘의 실행 시간이 일정하게 유지되고 입력 크기에 따라 달라지지 않는다는 것을 의미

- O(1) 알고리즘의 실행 시간은 입력 크기에 관계없이 항상 동일한 시간
- 인덱스를 사용하여 배열의 요소에 접근

#include <iostream>
using namespace std;

int main()
{

    int i, n = 8;
    for (i = 1; i <= n; i++) {
        cout << "Hello World!\n";
    }
    return 0;
}

int getElement(int arr[], int index) {
    return arr[index]; // 배열의 특정 요소에 접근, O(1)
}

 

선형 시간 복잡도 O(n): n번 루프

- 루프 변수가 일정한 양만큼 증가/감소하는 경우 루프의 시간 복잡도는 O(n)으로 간주

- O(n)으로 표시되는 선형 시간 복잡도는 알고리즘의 실행 시간이 입력 크기에 비례하여 증가하는 정도를 측정

- O(n) 알고리즘에서 실행 시간은 입력 크기에 따라 선형적으로 증가

- 정렬되지 않은 배열에서 요소를 검색하거나 배열을 반복하고 각 요소에 대해 일정한 양의 작업을 수행하는 것은 O(n) 연산

- 크기가 n인 입력에 대해 알고리즘은 n단계를 거쳐 연산을 완료

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) { // 배열의 각 요소에 접근, O(n)
        cout << arr[i] << " ";
    }
    cout << endl;
}

2차 시간 복잡도 O(n^c ): 중복 루프

- 중첩 루프에서 가장 안쪽 문장이 실행되는 횟수

- 크기가 n인 입력에 대해 알고리즘은 n * n 단계를 거쳐 작업을 완료

- 각 요소에 대해 전체 입력을 반복하는 중첩 루프, 각 반복에 대해 일정한 양의 작업을 수행

// Here c is any positive constant
for (int i = 1; i <= n; i += 5) {
    for (int j = 1; j <= n; j += 5) {
        // some O(1) expressions
    }
}

대수 시간 복잡도 O(Log n) 

- 루프 변수가 상수 양으로 나누어지거나 곱해지는 경우 

- 문제의 크기를 1/2로 줄이는데 일정한 시간이 걸림

- 재귀 함수의 재귀 호출의 경우 시간 복잡도는 O(Logn)으로 간주

- 이진 검색(반복 구현 참조)의 시간 복잡도

#include <iostream>
using namespace std;

int main()
{

    int i, n = 8;
    for (i = 1; i <= n; i=i*2) {
        cout << "Hello World!\n";
    }
    return 0;
}

대수 시간 복잡도 O(Log Log n):

- 루프 변수가 일정한 양만큼 기하급수적으로 감소/증가하는 경우 

 

#include <iostream>
#include <cmath>
using namespace std;

int main()
{

    int i, n = 8;
    for (i = 2; i <= n; i=pow(i,2)) {
        cout << "Hello World!\n";
    }
    return 0;
}

 

 

 

ex) 

Q. 100명의 학생이 있는 교실에서 누군가에게 빌려준 펜을 찾는 방법

 

• O(n²): 첫 번째 학생에게 펜을 가지고 있는지 묻고, 그 학생에게 다른 99명에게도 펜이 있는지 물어보는 방식을 반복합니다. 이 경우, 모든 학생에게 일일이 다른 학생에게도 물어본다.
• O(n): 각 학생에게 한 명씩 차례대로 펜을 가지고 있는지 물어본다.
• O(log n): 교실을 두 그룹으로 나누고, 펜이 왼쪽 또는 오른쪽에 있는지 묻습니다. 찾고자 하는 그룹을 계속해서 절반씩 줄여가며 질문을 반복하여 한 명이 남을 때까지 진행

 

 

• 정렬되지 않은 경우: 순차 탐색(O(n))이 최선입니다.
• 정렬된 경우: 이진 탐색(O(log⁡n))이 더 효율적입니다.

// 순차 탐색

#include <iostream>
#include <vector>
#include <string>

int findPenSequentially(const std::vector<std::string>& students) {
    for (int i = 0; i < students.size(); i++) {
        if (students[i] == "pen") { // "pen"을 가진 학생 찾기
            return i; // 찾으면 인덱스 반환
        }
    }
    return -1; // 찾지 못한 경우
}

int main() {
    std::vector<std::string> students(100, ""); // 100명의 학생, 기본적으로 빈 값
    students[23] = "pen"; // 예시로 24번째 학생에게 펜을 줌
    
    int penIndex = findPenSequentially(students);
    if (penIndex != -1)
        std::cout << "펜을 가진 학생은 " << penIndex + 1 << "번째 학생입니다.\n";
    else
        std::cout << "펜을 찾을 수 없습니다.\n";

    return 0;
}