1. 반복문

1.1 입력 크기의 변수가 여러 개인 경우

void func1(int n, int m){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j *= 2)
        printf("Yeah!\n");
    }
}

$\Theta\left(n \log m\right)$

1.2 복합

void func2(int n, int m){
    for(int i = 1; i <= n; i++)
        printf("Yeah!\n");

    for(int i = 1; i <= n; i *= 2)
        for(int j = n; j >= 1; j /= 2)
            printf("Yeah!\n");

    for(int i = 1; i <= m; i *= 2)
        for(int j = m; j >= 1; j /=2)
            printf("Yeah!\n");
    
    for(int i = 1; i <= 100000; i++)
        printf("Yeah!\n");
}

$\Theta\left(n+\log ^{2} m\right)$

2. 재귀함수

재귀함수 시간복잡도 구하기:

• 마스터 정리(가능하다면)
• 재귀 호출이 서로 다른 파라미터를 가지면 재귀트리
• 같은 파라미터를 가진다면 치환법
• 재귀식에서 재귀와 관련 없는 여러 연산이 있는 경우, 그 중에서 가장 큰 시간복잡도를 가지는 연산을 재귀식의 최종 시간복잡도에 반영

마스터 정리:

2.1 병합정렬

void mergesort(int low, int high){
    int mid;
    if(low < high){
        mid = (low + high) / 2;
        mergesort(low, mid);
        mergesort(mid + 1, high);
        merge(low, mid, high);
    }
}

$\Theta(n \log n)$

2.2 이진탐색

int binarySearch(int arr[], int low, int high, int target) {
    if (low > high) {
        return -1;
    }
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] > target) {
        return binarySearch(arr, low, mid - 1, target);
    } else {
        return binarySearch(arr, mid + 1, high, target);
    }
}

$O(\log n)$

2.3 이진 트리 높이 계산

struct Node {
    int data;
    Node* left, *right;
};

int height(Node* node) {
    if (node == NULL) {
        return 0;
    }
    return max(height(node->left), height(node->right)) + 1;
}

$O(n)$

2.4 연속된 자연수의 합

int sumNaturalNumbers(int n) {
    if (n == 1) {
        return 1;
    }
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += i;
    }
    return sum + sumNaturalNumbers(n - 1);
}

$O\left(n^{2}\right)$

2.5 피보나치 수열

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

$O\left(2^{n}\right)$

2.6 하노이 탑

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod << endl;
        return;
    }
    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
    cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << endl;
    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

$O\left(2^{n}\right)$

3. 복잡한 복잡도 문제

3.1

void func8(int n){
    int s = 0;
    for(int i = 1; i * i <= n; i++)
        s += i;
}

$O(\sqrt{n})$

3.2

void func9(int n){
    int s = 1;
    for(int i = 1; s <= n; i++)
        s += i;
}

$O(\sqrt{n})$

3.3

void func10(int n){
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            printf("Yeah!\n");
}

$O\left(n^{2}\right)$

3.4

void func11(int n){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j += i)
            printf("Yeah!\n");
}

$O(n \log n)$

3.5

void func12(int n){
    if(n <= 0)
        return;
    else
        for(int i = 1; i <= 3; i++)
            func12(n - 1);
}

$O\left(3^{n}\right)$

3.6

void func13(int n){
    if(n <= 0)
        return;
    else
        for(int i = 1; i <= 3; i++)
            func13(n / 3);
}

$O(n)$

3.7

void func14(int n){
    if(n <= 0)
        return;
    else
        for(int i = 1; i <= 8; i++)
            func14(n / 2);
}

$O\left(n^{3}\right)$

3.8

void func15(int n){
    if(n <= 0)
        return;
    else{
        for(int i = 1; i <= 8; i++)
            func(n / 2);
        
        for(int i = 1; i<= n; i++)
            for(int j = 1; j <= n; j++)
                for(int k = 1; k <= n; k++)
                    printf("Yeah!\n");
    }
}

$O\left(n^{3} \log n\right)$