[Algorithms] 알고리즘이란?

알고리즘의 정의는

a finite set of instructions for solving a problem

 
이다. 어떠한 문제를 푸는 방법을 정의한 것이다.

즉 프로그램이라는 것은 Data Structure + Algorithms이라고 볼 수 있다. 
그렇다면 어떠한 문제가 있을 때 그것을 해결할 수 있는 알고리즘은 많이 있을 것이고
그 알고리즘 간에 어떤것이 효율적인가를 결정할 수 있어야한다.

그래서 나온 개념이 복잡도(Complexity)이며 어떤 알고리즘의 complexity는 보통 Big-O notation으로 많이 나타내는데
엄밀히 따지면 Big-theta notation으로 나타내야 한다.

그리고 어떤 알고리즘이 어떠한 theta(x)의 복잡도를 가지면 그 알고리즘은 order of x의 복잡도를 가진다고 한다.


알고리즘 order의 순서는 다음과 같다.

1 < lg n < n < n lgn < n^2 < n^3 < .......

n의 세제곱을 넘어가는 오더를 가지는 알고리즘은 거의 쓰레기 알고리즘이라고 보면 되며
보통 효율적이라고 말하는 알고리즘들은 n log n 오더를 가지는 경우가 많다.