Time Complexity(시간 복잡도) (진행중)

Time Complexity(시간 복잡도) (진행중)

고등학교 때 이런 그래프를 많이 봤었던 것 같다.. 다시 보니 반갑기도 하고 만나고 싶지는 않았지만

알고리즘을 이번 주에 보면서 레퍼런스에서 자주 시간의 복잡도에 대해서 계속 언급도 있고, 이 내용을 보긴 했지만 기억에 잘 남지 않아 배웠던 내용들을 다시 써보면서 되새김을 해볼려고 합니다.

@시간 복잡도

문제를 해결하기 위해서 알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려해야한다고 하는데 그 의미는

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 입니다.

아마 저희가 추구해야하는 방향은 입력 값은 커지는데도 불구하고 걸리는 시간은 최소화 한다는 것 아닐까요?

시간 복잡도는 주로 빅-오 라는 표기법으로 나타낸다고 합니다.

@ Big-O 표기법

시간 복잡도를 표기하는 방법은 다음과 같습니다.

Big-O

Big-Ω(빅-오메가)

Big-θ(빅-세타)

위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법 입니다. 이 중에서 Big-O 표기법이 가장 자주 사용이 된다고 합니다.

빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 시간까지 고려할 수 있기 때문입니다. '최소한 특정 시간 이상이 걸린다.' 혹은 '이 정도 시간이 걸린다'를 고려하는 것보다 '이 정도 시간까지 걸릴 수 있다.'를 고려해야 그에 맞는 대응이 가능합니다.

1. O(1)

빅오 표기법은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 를 표기하는 방법입니다.

O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘지나지 않습니다.

값을 검색할 때, 객체에서 키를 알거나 배열에서 인덱스를 알고 있으면 항상 한 단계를 거치는 것이라고 생각해도 좋을 것 같습니다.

고딩 때 배운 기억으로는 y = 1인 그래프라고 생각하면 될 것 같습니다. 예시로 알아봅시다.

function 0_1_algorithm(arr, index) { return arr[index]; } let arr = [1,2,3,4,5]; let index = 1; let result = 0_1_algorithm(arr, index); console.log(result); // 2

위의 알고리즘(예시)에서는 입력값의 크기가 아무리 커져도 즉시 출력값을 알 수 있고 얻어 낼 수 있습니다.

2. O(n)

O(n)은 linear complexity(선형 복잡도)라고 부르며, 입력값이 증가함에 따라 시간 또한 1:1 비율로 증가하는 것을 의미합니다.

ex) 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현을 했다고 한다면, 그 알고리즘은 O(n)의 시간 복잡도를 가지고 있다 라고 할 수 있습니다.

대략적으로 Linear search, for 문을 통한 탐색을 생각하면 됩니다.

function O_n_algorithm(n) { for(let i = 0; i < n; i++) { // do something for 1 second } } function another_O_n_algorithm(n){ for(let i = 0; i < 2n; i++) { // do something for 1 second } }

O_n_algorithm 함수에선 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가합니다. 즉 입력값이 증가함에 따라 값은 비율로 걸리는 시간이 늘어나고 있습니다.

그렇다면 함수 another_O_n_algorithm 은 어떻게 될까요? 입력값이 1증가할때마다 코드의 실행 시간이 2초씩 증가합니다.

위를 보고, '아! 그렇다면 이 알고리즘은 O(2n) 이라고 표현하겠다'라고 생각을 할 수도 있습니다. 그러나, 이 알고리즘 또한 빅오 펴ㅛ기법으로는 O(n)으로 표기한다고 합니다.

O(log n)

O(log n)은 logarithmic complexity(로그 복잡도) 라고 부르며 빅오 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가집니다.

자료구조에서 배웠던 BTS(Binary Search Tree)를 생각해보자면.. 큐를 이용해서 경우의 수를 줄이는 방법으로, 원하는 값을 탐색할 때 노드를 이동할 때마다 경우의 수가 절반으로 줄어듭니다. up & down을 예로 보자면,

1~100 중 하나의 숫자를 A가 고른다. 30이라고 하자. 50(가운데) 숫자를 제시하면 50보다 작기에 down을 외친다. 1~50 중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다. 25보다 크므로 up을 외친다. 경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다.

매번 숫자를 제시할 때마다 경우의 수가 절반이 줄어들기 때문에 최악의 경우에도 7번이면 원하는 숫자를 찾아낼 수 있게 됩니다.

BTS의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)입니다.

from http://my-cording-story.tistory.com/97 by ccl(A) rewrite - 2021-08-28 18:26:09