13

ビッグオー記法については学習しましたが、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とどのように関係していますか?

4

2 に答える 2

12

この表記は、関数の実行にかかる最大時間 (より具体的にはステップ) を指します。

T(n) は O(n) よりもはるかに具体的です。たとえば、入力に対してn^2+n+1実行するステップが必要なプログラムがあるとします。

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

詳細については、こちらをご覧ください。

于 2012-11-29T03:13:52.607 に答える
0

個人的にはこの表記法を見たことがありませんが、漸近上限 (big-O) と漸近下限の両方である "big-Theta" (Θ) を指していると思われます。

関連: Big-Omega (Ω) は、漸近的な下限 (big-O のミラーリング) を表すために使用されます。

于 2012-11-29T03:14:00.430 に答える