Que signifie la notation T (n)?

Question

Nous avons appris à propos de la notation grand O, mais je vois aussi souvent T (n). Par exemple,

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 

Je crois que c, d, e, ... sont supposés être des constantes nommées arbitrairement.

Que signifie T (n/2)? aussi comment est la notation T liée au grand O?

Answer 1

Cette notation fait référence à la durée maximale (ou, plus précisément, aux étapes) qu'une fonction prend pour s'exécuter.

T (n) peut être beaucoup plus spécifique que O (n); par exemple, disons que vous avez un programme que pour toute entrée, nécessite n^2+n+1 étapes à exécuter:

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

Plus d'informations peuvent être trouvées here.

Answer 2

Personnellement, je n'ai jamais vu cette notation auparavant, mais je pense qu'elle se réfère à "big-theta" (Θ), qui est à la fois une limite supérieure asymptotique (big-O) et une limite inférieure asymptotique. Egalement lié: Big-Omega (Ω) est utilisé pour désigner simplement une limite inférieure asymptotique (big-O en miroir).