Data Structure & Algorithm/Algorithm
-
[Algorithm] 시간 복잡도 (BIG O 표기법) 정리Data Structure & Algorithm/Algorithm 2025. 12. 15. 16:18
📌 목차 ◦ 시간복잡도◦ 시간복잡도 계산 방법 📌 시간복잡도 ⚡정의컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도일반적으로 시간 복잡도는 점근 표기법을 이용하여 나타낸다. ** 점근 표기법 ( Asymptotic Notation ) : 함수의 증감 추세를 비교하는 표기법이며, 란다우 표기법이라고 부르기도 한다.Big-O (상한, 최악의 경우), Big-Omega (하한, 최선의 경우), Big-Theta (평균, 상하한의 교집합) 표기법 등이 있다. 시간 복잡도와 로직의 수행 시간은 비례하므로 시간 복잡도 수치가 작을수록 효율적인 알고리즘임을 뜻한다.아래의 예시에서 위부터 간단하고, 아래로 갈수록 복잡해진다. • O(1) 의 상수 형태 • O(log₂n) 의 로그 형태 • ..