시간 복잡도에 관하여

알고리즘은 어떤 목적을 달성하거나 결과물을 만들어내기 위한 일련의 과정들을 얘기한다.
같은 풀이라도 코드에 따라 각양각색의 알고리즘이 있을 수 있다.
어떤 알고리즘이 가장 효율적인가를 판단하기 위해서는 코드의 완료까지 걸리는 절차의 수로 결정한다.
따라서 같은 작업을 수행하는데 걸리는 절차가 적은 알고리즘이 훌륭한 알고리즘이다.
이것을 수치화 한것이 시간 복잡도이다.

예제로 알아보는 시간 복잡도 개념

• 실행 시간의 개념을 '함수나 알고리즘 수행에 필요한 스텝(step) 수'라고 정의하도록 하겠다. 왜냐하면 실행 시간은 같은 알고리즘이라도 컴퓨터 하드웨어의 성능에 따라 달라지기 때문에 초 단위로 표현하는 것은 어렵다

function multiply(arr, mult) {               //  cost    times
  const n = [];                              //   c1       1

  for (let i = 0; i < arr.length; i++) {     //   c2      N+1
    n = arr[i] * mult                        //   c3       N
  }
  return n                                   //   c4       1
}

위의 코드를 보자.
각 라인 별로 수행되는 cost(스텝 수)는 각각 c1, c2, c3, c4 이렇게 상수로 정해놓고 각 라인이 실행되는 횟수를 구해보면, 배열의 arr가 N이라고 했을 때 각각1, N+1, N, 1 이다
그리고 전체 실행 시간을 N에 대한 함수로 표현하면

T(N) = c1 + c2(N+1) + c3N + 1
= (c2 + c3)N + (c1 + c2 + 1)
= aN + b

이때 N의 값이 매우 작다면 실행시간은 굉장히 줄어들 것이다.
그렇다면 N의 값이 무한대로 증가하게 된다면 이 함수의 실행시간은 어떻게 될까
일단 최고차항을 제외한 나머지 항들은 N에 비해 영향력이 상대적으로 많이 줄어드므로 제거한다.
이렇게 최종적으로는 N만 남고 이를 표기하면 𝚹(N) 이 된다.

 

이렇게 N이 무한대를 향해 커질 때 어떤 단순한 형태로 접근하는지 분석을 했는데, 이런 분석 방식을 점근적 분석 이라고 한다. 그리고 점근적 분석을 통해 근사된 함수를 𝚹(N)로 표기하는 것을 점근적 표기법이라고 한다.

 

함수나 알고리즘에서 시간 복잡도의 개념은 '함수의 실행 시간을 표현하는 것'을 의미하고 주로 '점근적 분석을 통해 실행 시간을 단순하게 점근적 표기법으로 표현한다'

최선과 최악의 상황으로 구분

function Search(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // 타겟 값을 찾았을 때 인덱스를 반환합니다.
    }
 }

arr에 1부터 1000의 값이 순서대로 들어있다고 하자, 이때 1을 찾을 때와 1000을 찾을 때에는 함수의 실행 시간이 차이가 난다
그래서 best case와 worst case로 나눌 수 있다.
best case는 0번째 index에 존재할 때이고 1번의 탐색만 하면 된다.
worst case는 마지막에 존재하거나 존재하지 않을 때를 가정하므로 최소 N번의 탐색이 필요하다.

그리고 이런 특징을 바탕으로 함수의 실행 시간을 문장으로 서술한다면

• 하한선(lower bound)을 기준으로 서술 : 함수 실행 시간은 아무리 빨라도 상수 시간 이상
• 상한선(upper bound)을 기준으로 서술 : 함수 실행 시간은 아무리 오래 걸려도 N에 비례하는 정도 이하

그리고 이 내용들을 각각 기호로 표기하면 아래와 같다.

• 𝝮(1) - 하한선
• O(N) - 상한선

여기서 𝝮(big omega)는 lower bound를 의미하고, O(big Oh)는 upper bound를 의미한다. 𝝮(1)의 1이 의미하는 것은 상수(constant)를 의미한다. 즉 N과 상관없이 N이 크던 작던 상수라는 의미이고, O(N)의 N이 의미하는 것은 N에 비례하는 형태를 의미한다.

정리하자면 이 함수의 시간 복잡도는

• 𝝮(1) 라고도 할 수 있고
• O(N) 라고도 할 수 있다.

하지만 보통 일반적으로 하한선보다는 상한선을 더 궁금해하기 때문에 주로 O(N)을 많이 쓴다고 볼 수 있다.

from 쉬운코드 : https://youtu.be/tTFoClBZutw?t=782

 

 

대표적인 시간 복잡도를 빠른 순서부터 나열하면 아래와 같다. 오른쪽으로 갈수록 더 오래 걸린다고 이해하면 된다.

O(1) < O(logN) < O(N) < O(N*logN) < O(N^2) < O(2^N) < O(N!)

http://bigocheatsheet.com/

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell

 

[참고 블로그] - https://easy-code-yo.tistory.com/13  

 

알고리즘에서 어떻게 판별할 수 있는지 왜 썼는지 추가내용!