시간복잡도

나는 지금까지 시간복잡도를 배웠지만, 시간복잡도를 생각하지않고 코딩을 해왔다.

단순히 이게 효율적일까 ? 아 이거보단 이게 효율적일것같은데 ?

라는 생각을 가지고 코딩을 했는데.. 생각을 해보니 시간복잡도를 배운것들 까먹었다.

앞으로는 로직을 짜고 시간복잡도를 계산 해보고 다른 로직도 구성해본 뒤 가장 최적의 로직을 짜도록 노력할것이고,

TIL에 업로드 하게 된다면 대부분은 시간복잡도를 계산하여 주석으로 달겠다.

 

이렇게 시간복잡도를 사용하려면내가시간복잡도를 잘 알아야하니 복습을 해보도록 하겠다.

 

시간복잡도를 표현하는 방법은 여러가지가 있는데, 대부분이 사용하는 "빅오표기법"을 사용하겠다.

빅오표기법이란 ? - "최악의 경우" 얼마나 시간이 걸릴지를 나타내는 표기법이다.

 

상수시간O(1) : 입력 데이터의 크기와 관계없이 항상 일정한 시간에 작업이 끝나는 경우

int value = arr[5];  // 5대신 1, 2, 8, 7 등 어떤 값이들어가도 시간복잡도는 O(1)이다.

 

 

선형시간 O(n) : 입력 데이터의 크기에 비례하여 시간이 걸리는 경우

for (int i = 0; i < n; i++) {
    // n의 값에 따라 "O(n)"  n 이 결정됨
}

 

 

로그시간 O(log n) : 입력 데이터의 크기가 커질  반으로 줄어드는 방식으로 시간이 걸리는 경우

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

 

 

이차시간 O(n ² ) : 데이터가 늘어남에 따라 제곱에 비례해서 시간이 걸리는 경우 (이차원배열 등 중첩된 반목문)

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
    }
}

 

 

솔직히 나는 로그시간이 이해가 안됐다

 

그렇다면 빅오표기법을 아직 이해를 못한것이다.

 

정렬된 배열이 있다고 가정해보자

[1, 2, 3, 5, 7, 9, 11, 13, 15, 17, 19]

 

여기서 11을 찾고싶으면 어떻게 할까 ?

 

일반적이라면

 

처음부터 살펴본다.

 

그러면 6번째에 찾았다.

 

하지만 빅오표기법은 최악의 경우이니 O(6)이 아닌 O(11) 시간 이다.

 

그러면 다시 아까 로그예제를 생각하고 살펴보자

 

배열의 중간값은 9이다

 

찾는 값은 11이고 9보다 크니 9보다 큰 값만 보면

 

5개의 값이 나온다. 여기서 또 중간값인 15에서 15보다 작은값만 보면

 

11과 13이 남는데, 예제의 식을 이용하면 11을 발견 할 수 있다.

 

이런식으로 매번 절반을 보고 +-하여 값을 찾아낸다면 한번 비교를 진행할 때 마다 탐색범위가 절반으로 줄어들기에

이것을 로그시간 복잡도라고 한다.