빅 오 표기법에 대해 알아보기 전에 간단히 알고 가야할 것은 바로...!
시간 복잡도(Time Complexity)
시간 복잡도는 알고리즘이 수행될 때, 몇번의 연산이 필요한지를 수식으로 표현한 것으로, 그 시간 복잡도를 간단하게 나타내는 표기법이 바로 빅 오 표기법이다.
공간 복잡도라는 개념도 있는데, 그건 나중에 생각해보자...
빅 오 표기법, Big O Notation
빅 오 표기법은 알고리즘이 실행되는데 얼마나 오래 걸리는지(연산이 얼마나 필요한지) 즉, 시간 복잡도를 간단히 표현하는 표기법이다. 알고리즘이 얼마나 효율적인지를 확인하려면, 빅 오 표기법을 확인하면 된다.
빅 오 표기법은 알고리즘과 함수의 효율성을 판단하는 지표가 된다.
동일한 태스크를 수행하는 다른 형태의 두 함수가 있다고 생각해보자.
그 두 함수의 빅 오 표기법을 분석하게 되면, 어떤 함수가 더 효율적인 알 수 있다.
특히 Input 값이 엄청 커지는 경우, 즉 방대한 scale의 Input이 입력되는 경우에는 시스템의 메모리나 연산 능력의 한계치에 가까워질 수 있으므로, 함수의 효율성을 고려한 코딩이 필요해진다. 이때 빅 오 표기법이 특히 중요해진다.
왜냐하면 빅 오 표기법이 어떤 알고리즘이나 함수 따위가 더 효율적인지 판단하는 중요한 지표가 되기 때문이다!
💡 아하! 이제 빅 오 표기법은 시간 복잡도를 간단히 나타내는 표기법이니까 함수나 알고리즘의 효율성을 판단할 수 있겠구나.
로 이해하면 된다!
그 용도까지 이해했으니, 빅 오 표기법의 예제를 토대로 어떤 알고리즘이나 함수가 효율적인지 알아보자.
빅 오 복잡도 차트
Source : https://dyarleniber.github.io/notes/big-o/
빅 오 복잡도를 나타낸 표 인데, 있는 표 그대로 이해해보자.
x축은 input, elements의 크기 값 n으로 함수나 알고리즘에 대입되는 데이터의 덩치이고, y축은 그 input에 상응하는 연산의 횟수다.
그러니까, n에 해당하는 값이 커질수록 필요한 연산의 값이 알고리즘이나 함수에 따라 크게 다르다는 것을 이 표를 통해 알 수 있다.
💡아하! 그러니까 이 표를 토대로
- O(log n), O(1) -> 훌륭한 효율
- O(n) -> 적당한 효율
- O(nlog n) -> 나쁜 효율
- O(n^2), O(2^n), O(n!) -> 최악의 효율
임을 알 수 있다.
즉, scalable한 코딩을 위해서는 효율을 극대화하기 위해서, O(log n), O(1), O(n) 표기법으로 나타낼 수 있는 알고리즘을 사용하도록 하는 것이 바람직하다.
하지만 항상 효율적인 알고리즘이 좋다고만 할 수는 없는데, 극단적으로 효율성만을 추구하서 readablity 즉, 코드를 다른 사람이 읽었을 때 무슨 기능을 하는지에 대해 전달력이 현저하게 떨어진다면 그 역시 좋은 코드라고 할 수 없다.
그러므로 readability는 최소한 확보하되, 가장 scalable한 알고리즘을 찾아 사용하여 밸런스를 찾는게 중요하다.
