표기 T (n)은 무엇을 의미합니까?

Question

우리는 큰 O 표기법에 대해 알았지 만, 종종 T (n)도 보았습니다. 예를 들면,

public static Comparable[] mergeSort(Comparable[] A, int low, int high) { 
    if (low < high) { //at least 2 elements?    //cost = c 
    int mid = (low + high)/2;        //cost = d 
    Comparable[] A1 = mergeSort(A, low, mid);    //cost = T(n/2) + e 
    Comparable[] A2 = mergeSort(A, mid+1, high);   //cost = T(n/2) + f 
    return merge(A1,A2);         //cost = g n + h 
    } 
    .... //cost = i 

나는 c, d, e ...가 임의로 명명 된 상수라고 생각합니다.

T (n/2)는 무엇을 의미합니까? 또한 T 표기법은 큰 O와 관련이 있습니까?

Answer 1

이 표기법은 함수를 실행하는 데 걸리는 최대 시간 (또는 더 구체적으로 단계)을 나타냅니다.

T (n)은 O (n)보다 훨씬 더 구체적 일 수 있습니다. 예를 들어, 당신은 어떤 입력, 실행 n^2+n+1 단계를 필요로하는 프로그램이 있다고 가정 해 봅시다 :

T(n) = n^2+n+1 
O(n) = n^2 

상세 정보 here를 찾을 수 있습니다.

Answer 2

나는 개인적으로이 표기법을 처음 보지 못했지만, 나는 그것이 근원적 인 상한 (big-O)과 점근 적 하한선 인 "big-Theta"(Θ)를 언급한다고 생각한다.

관련 항목 Big-Omega (Ω)는 점근 적 하한 (미러링 big-O)을 나타내는 데 사용됩니다.