[TIL] 시간복잡도 big O 표기법

시간복잡도 O(1)

---

public int sum (int n, int b) {
    return n+b;
}

sum 함수는 두 개의 매개변수 n, b를 사용해 n과 b의 합을 반환한다. n과 b의 값에 관계없이 함수는 하나의 더하기 연산을 수행하고 즉시 결과를 반환하기에 입력 값에 관계없이 일정한 수의 작업을 실행하므로 동일한 시간이 걸린다.

시간복잡도 O(log n) - 이진검색 ( Binary Search )

---

정렬된 배열에서 효율적으로 검색하는 알고리즘이다. 간단한 예로 1부터 10까지의 배열이 있고 찾는값이 4라고 했을 때 배열의 중간값인 5보다 큰지 작은지 비교하고 또 다시 1부터 5까지의 중간값인 3보다 크거나 작은지 비교하며 동일한 반복을 진행한다.

시간복잡도 O(n)

---

public int sum (int n) {
    int result = 0;
    for (int i=0 ; i<n ; i++) {
        result += n+i;
    }
    return result;
}

반복문에서 입력받은 매개변수 n만큼 루프가 실행된다. 매개변수 n이 증가하는 만큼 시간복잡도 또한 증가하고 입력받은 매개변수 n의 값이 4라고 가정했을 때 가로나 세로의 길이가 4 * 1의 직사각형이 생기는 개념인 O(4)로 이해하면 편하다.

시간복잡도 O(n^2)

---

public int sum (int n) {
    int result = 0;
    for (int i=0 ; i<n ; i++) {
        for (int j=0 ; j<n ; j++) {
            result += i+j;
        }
    }
    return result;
}

두 개의 반복문이 겹쳐서 사용된다. 확인할 것은 해당 반복문이 어떤 값만큼 실행되는지 확인해야하고 각각의 반복문 모두 입력받은 매개변수 n만큼 진행한다는 것이다. 입력받은 매개변수 n의 값이 4라고 가정했을 때 가로와 세로의 길이가 4 * 4인 정사각형이 생기는 개념인 O(4^2)로 이해하면 편하다.

시간복잡도 O(nm)

---

public int sum (int n, int m) {
    int result = 0;
    for (int i=0 ; i<n ; i++) {
        for (int j=0 ; j<m ; j++) {
            result += i+j;
        }
    }
    return result;
}

O(n^2)과 동일한 이중반복문이다.하지만 주의해서 봐야할 것은 각각의 반복문 실행 횟수가 다르다는 부분이다. 첫 반복문은 매개변수 n만큼 실행되고 두 번째 반복문은 배개변수 m만큼 실행되어 각각 n=4 m=3 이라고 가정했을 때 4 * 3의 직사각형이 생기는 개념인 O(4 * 3)으로 이해하면 편하다.

시간복잡도 O(n^3)

---

public int sum (int n) {
    int result = 0;
    for (int i=0 ; i<n ; i++) {
        for (int j=0 ; j<n ; j++) {
            for (int k=0 ; k<n ; k++) {
                result += i+j+k;   
            }
        }
    }
    return result;
}

반복문을 3번 사용하는 것으로 각각의 반복문의 실행 횟수는 입력받은 매개변수 n으로 모두 같다. n=4로 가정했을 때 4 * 4 * 4의 큐브가 생기는 개념인 O(4^3)으로 이해하면 편하다.

시간복잡도 O(2^n), O(m^n)

---

O(n^2), O(n^3)과 비교했을 때 데이터가 증가하면 시간도 더 증가하며 아래의 피보나치수열을 예로들 수 있고 트리의 높이만큼 진행하게된다.