符號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

我以前從未見過這種符號，但我懷疑它是指「大-Theta」（Θ），它既是一個漸近上界（大-O）又是一個漸近下界。

此外相關：Big-Ω（Ω）用於表示漸近下界（鏡像big-O）。