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

更多信息可以在这里找到.