매일매일
빅오 표기법 (Big O Natation)
CS/알고리즘 2023. 3. 28. 02:13

빅오 표기법 좋은 코드를 판단할 때는 여러가지 기준이 있을 수 있지만 빅오 표기법은 객관적이며 변하지 않는 기준으로 코드의 효율성을 비교하기위한 표기법이다. 시간 복잡도과 공간 복잡도를 나타나는데 주로 사용된다. 시간 복잡도 알고리즘이 얼마나 빠르게 실행하지를 나타낸다. 이름은 시간 복잡도이지만 실제 코드가 실행되는 시간을 기준으로 하지 않고 연산 갯수를 기준으로 판단한다. 왜냐라면 시간은 가변적이기 때문이다. 시간은 컴퓨터의 사양에 따라서 변할수도 있고 심지어 같은 컴퓨터에서도 실행할 때마다 시간이 조금씩 바뀐다. 반면 연산 갯수는 어떤 컴퓨터에서든 동일하기 때문에 연산 갯수를 기준으로 판단한다. 연산 갯수 연산 갯수는 정확한 연산 갯수를 의미하진 않고 단순화한 갯수를 의미한다. 예를 들어 아래의 함수..