시간 복잡도

https://refreshment-wg.tistory.com/58

Array & Linked list

 Linked list와 array의 차이에 대해 적으면서 시간복잡도라는 개념이 나와 정리해보았습니다...

먼저 알고리즘에서 로직을 코드로 구현할 때 시간복잡도를 고려한다는 것은

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

 

 즉. 시간복잡도는 문제를 해결하는데 걸리는 시간과 입력한 함수 관계로, "연산의 횟수(시행 횟수)"를 센다는 것입니다.

상대적으로 불필요한 연산을 제거하여 알고리즘의 분석을 조금 더 간편하게 하는 목적으로 표기하는 방법입니다.

 실행 시간으로 시간복잡도를 계산할 경우, 측정을 위한 완성된 프로그램이 필요하며, 모든 플랫폼에서 동일한 결과를 산출하지 못합니다. 

 

 알고리즘의 성능평가는 최선, 최악 평균 유형으로 구분됩니다. 

알고리즘 분석 시, 평균 성능과 최악의 성능이 가장 많이 활용됩니다. 알고리즘이 복잡해질수록 평균의 경우가 구하기가 어려워져서 최악의 경우로 알고리즘 성능을 파악합니다.

 

 최선의 경우는 최적의 입력을 한 상태에서 작업을 완료하는데 가장 빠른 시간이 걸리는 것입니다.

반대로 최악의 경우는 자업완료까지 가장 느린 시간이 소요되며, 평균의 경우는 여러가지 다른 경우의 수를 입력해 총 실행시간을 계산하고 시행 횟수로 나눕니다.

 

 

 시간 복잡도를 표기하는 방법 중, Big-O 표기법이 있습니다. 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는가?를 표기하는 방법입니다. 

l = [1, 2, 3]

for n in l:
    print(n)

 예를 들어, 위 함수에서 리스트 l에 들어있는 데이터가 3개이기 때문에 3번 돌아갑니다. 리스트 안에 있는 갯수를 n이라 하고, n이 커질수록 알고리즘이 실행되는 횟수가 늘어납니다.  n의 갯수만큼 실행되기 때문에 위의 알고리즘의 시간복잡도는 O(n)이 됩니다. 여러 유형에 대해 설명해보겠습니다.

1. O(1)

 O(1)은 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않습니다. 즉 입력값의 크기와 관계없이 즉시 출력값을 얻을 수 있다는 말입니다. 

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

 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있습니다. arr의 길이가 10000... 계속 커진다고 해도, 즉시 해당 index에 접근해 값을 반환할 수 있습니다.

2. O(n)

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

 

3. O(log n)

O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며, Big-o표기법 중 O(1) 다음으로 빠른 시간복잡도를 가집니다. Binary Search Tree의 값 탐색에서 쓰이는 로직으로, 경우의 수를 절반으로 줄여나가며 답을 찾을 수 있는 방법입니다.

 

4. O(n2)

O(n2)는 2차 복잡도(quadratic complexity)라고 하며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미합니다. 

 

5. O(2n)

O(2n)은 기하급수적 복잡도(exponential complexity)라고 부르며 Big-o표기법 중 가장 느린 시간복잡도를 가집니다. 구현한 알고리즘이 시간복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋습니다.

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

 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적 알고리즘입니다. n이 너무 크다면 결과를 반환받을 수 없을 수도 있어서 주의해야 합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

출처

https://velog.io/@leobit/%EB%B3%B5%EC%9E%A1%EB%8F%84Complexity

복잡도(Complexity) : 시간 복잡도

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬