[알고리즘] 기본 및 복잡도

알고리즘이란?

유한한 단계로 문제를 해결하는 로직이다. 컴퓨터가 어떤 일을 하는 수행의 단계적 방법이다.

효율적인 알고리즘

메모리 공간을 최적화 하는 공간적 효율성, 수행 시간에 대해 최소의 시간을 고려하는 시간적 효율성 고려해야한다. 

효율성이 즉 복잡도가 된다.

이러한 부분은 아키텍처, 자료구조, HW 환경, SW 환경 등 다양한 요소를 고려해야한다.

복잡도의 점근적 표기 Big-Oh

시간 복잡도를 입력 크기에 대한 함수로 표기할 수 있다. 이를 점근적 표기(Asymptotic Notation)라 한다.

가장 큰 예로 Big-Oh 표기법이 있다. Big-Oh는 최대 이런 시간이 걸린다는 의미를 가진다.

O(1)            :   상수 시간 (Constant time)

O(logn)        :   로그(대수) 시간 (Logarithmic time)

O(n)            :   선형 시간 (Linear time)

O(nlongn)     :   로그 선형 시간 (Log-linear time)

O(n제곱)       :   제곱 시간 (Quadratic time)

O(n세제곱)    :   세제곱 시간 (Cubic time)

O(2의n제곱)   :   지수 시간 (Exponential time)

작성자 : 히더