Big-O 표기법이란 빅오 표기법은 알고리즘의 효율성을 표현하기 위해 가장 많이 사용하는 표기법 중 하나이다. 알고리즘의 실행 시간 또는 공간 복잡도를 입력 크기에 대한 함수로 나타낸다. 최악의 경우를 표기하기 때문에 알고리즘 복잡도의 상한을 표현하기에 적합하다. 표기법은 아래와 같다. O(f(n)) n은 입력 크기를 나타내고, f(n)은 알고리즘의 복잡도를 표현하는 함수이다. 그 외 표기법으로는 Big-Ω 표기법: 최선의 경우의 복잡도를 표기. Big-Θ 표기법: 평균적인 경우의 복잡도를 표기. 컴퓨터공학에서는 항상 최악의 경우를 고려해야 하므로 주로 Big-O 표기법을 사용한다.
코딩하는 삶/Algorithm
[시간 복잡도(Time complexity)] 자료의 수 n이 증가할 때 시간이 증가하는 대략적인 패턴을 표현하는 방식. 보통 Big-O 표기법을 사용한다. 수치가 작을수록 효율적인 알고리즘이지만 문제에 따라 O(2^n) 또는 O(n!)등의 복잡한 알고리즘을 사용해야만 하는 경우도 존재한다. O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!) 함수를 설계할 때 최대 O(n log n)정도의 시간 복잡도를 가지게 하는 것이 바람직하다. O(1) - 상수 n에 관계없이 일정한 시간이 걸리는 알고리즘. 대부분의 경우에서 가장 단순하고 빠르다. stack의 push/pop 연산, 배열/큐 등의 원소에 대한 접근 등이 이에 해당한다. function fo..
