빅오2 [자료구조] 04. 빅오메가 표기법 & 빅세타 표기법 빅오메가 표기법 (Big Omega) ※ 수학적 정의 : 모든 n ≥ n0에 대하여 |f(n)| ≥ C|g(n)|을 만족하는 2개의 상수 C와 n0가 존재하면 f(n) = Ω(g(n))이다. ▶ 함수의 하한 (lower bound)을 표시한다. ▶ 예를 들어, f(n) = 2n +1일 때, n ≥ 5이면 2n + 1 < 10n이므로 f(n) = Ω(n)이다. ▶ 빅오 표기법이 Worst Case에 대한 표기법이라면, 빅오메가 표기법은 Best Case에 대한 표기법이다. 빅세타 표기법 (Big Theta) ※ 수학적 정의 : 모든 n ≥ n0에 대하여 C1|g(n)| ≤ |f(n)| ≤ C2|g(n)|을 만족하는 3개의 상수 C1, C2와 n0가 존재하면 f(n) = Θ(g(n))이다. ▶ 함수의 상한인.. 2021. 10. 21. [자료구조] 03. 알고리즘의 성능 분석(시간 복잡도, 빅오 표기법) "얼마나 효율적인가?" (시간/메모리/리소스) 1. 수행 시간 측정 (직접 구현 O ) → 동일한 하드웨어를 사용하여 실제 수행 시간을 측정한다. 2. 알고리즘의 복잡도 측정 (직접 구현 X) → 연산의 횟수를 계산하여 비교한다. (예측) → 연산의 횟수는 n의 함수 (n은 충분히 큰 양의 정수. 즉, 입력의 크기에 따른 연산 횟수를 계산한다.) 수행 시간 측정 2가지 방법 #include start = clock(); // 시작 전 check // 알고리즘 내용 삽입 부분 stop = clock(); // 종료 직후 check double duration = (double)(stop - start) / CLOCK_PER_SEC; #include start = time(NULL); //알고리즘 내용 삽입.. 2021. 10. 20. 이전 1 다음
