notation - 符号 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 .