Data Structure2 빅세타(Big Theta) 표기법 빅세타 표기법은 알고리즘의 평균적인 실행 시간 복잡도를 나타내는 방법입니다. 빅오(Big O)가 최악의 경우 상한선을, 빅오메가(Big Omega)가 최선의 경우 하한선을 나타낸다면, 빅세타는 이 둘의 중간이라고 볼 수 있습니다.빅세타 표기법의 주요 특징:정의: 함수 f(n)이 어떤 양의 상수 c1, c2와 n0가 존재하여 모든 n ≥ n0에 대해 c1 * g(n) ≤ f(n) ≤ c2 * g(n)을 만족할 때, f(n) = Θ(g(n))이라고 표기합니다.의미: 알고리즘의 실행 시간이 특정 함수의 상수 배 내에서 위아래로 봉투처럼 감싸진다는 것을 의미합니다.정확성: 빅오나 빅오메가보다 더 정확한 실행 시간 추정을 제공합니다.대칭성: f(n) = Θ(g(n))이면 g(n) = Θ(f(n))입니다.1. 선형.. 2024. 10. 19. 빅오(Big O) 표기법 빅오 표기법은 알고리즘의 시간 복잡도나 공간 복잡도를 표현하는 방법으로, 주로 최악의 경우 성능을 나타냅니다.1. O(1) - 상수 시간:설명: 입력 크기와 관계없이 항상 일정한 시간이 걸립니다.예시: 배열의 인덱스로 직접 접근#include int constant_time_access(int arr[], int index) {return arr[index];}int main() {int arr[] = {1, 2, 3, 4, 5};printf("%d\n", constant_time_access(arr, 2));return 0;}2. O(log n) - 로그 시간:설명: 입력 크기가 증가함에 따라 실행 시간이 로그적으로 증가합니다.예시: 이진 검색#include int binary_search(int ar.. 2024. 10. 19. 이전 1 다음