<aside> 🚨 알고리즘 성능 분석의 개념을 다루기 앞서 알고리즘 성능을 분석할 때 같은 컴퓨터, 같은 언어로 측정해야만 의미가 있습니다. 당연하게도 컴퓨터에 따라 언어에 따라 절대적인 시간 차이가 있기 때문입니다.

</aside>

Context

1. 시간 복잡도와 공간 복잡도

간단히 말해 시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 저장 공간이 필요한지에 따라 달라집니다. 물론 좋은 알고리즘은 실행 시간도 짧고 저장 공간도 적게 쓰는 알고리즘 입니다. 하지만 통상적으로 시간과 공간을 만족시키기는 어렵습니다. 이유는 아래와 같습니다.

1. 첫번째로, 시간과 공간은 반비례적인 경향이 있습니다.
2. 두번째로, 대용량 시스템이 보편화 되면서 공간 복잡도보다는 시간 복잡도가 우선이 되었습니다.
3. 마지막으로, 위와 같은 두 이유로 인해 알고리즘은 시간 복잡도가 중심이 되었습니다.

• 시간 복잡도(Time Complexity)
• 공간 복잡도(Space Complexity)

<aside> 📎 그럼에도 공간 복잡도의 대략적인 계산은 필요합니다. 현업에서 빅데이터를 다룰 때는 저장 공간을 고려해서 구현하는 경우도 있으므로 참고해주시길 바랍니다.

1. 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많습니다.
2. 그렇기 때문에 시간, 공간 복잡도 모두 제약 사항이 있는 알고리즘이 있습니다.
3. 기존 알고리즘 문제에 영향을 받아서, 면접 및 코딩테스트에서도 고려되어야 하는 때도 있습니다.

</aside>

2. Big-O notation

빅오 표기법(Big-O notation) 표기법 이란, 알고리즘에서 상대적으로 불필요한 연산을 제거하여 알고리즘의 분석및 측정을 보다 간편하게 시간 복잡도를 표기하는 방법을 말합니다. 보통 최악의 효율성(최장시간)을 기준으로 작성한 코드가 얼마나 효율적인지 판단합니다.

주요 빅오 표기법 시간크기 비교 O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

빅오 표기법의 의미