Explication de la grosse notation thêta et asymptotique

Big Omega nous indique la limite inférieure du runtime d'une fonction, et Big O nous indique la limite supérieure.

Souvent, ils sont différents et nous ne pouvons pas mettre de garantie sur le runtime - cela variera entre les deux limites et les entrées. Mais que se passe-t-il quand ils sont identiques? Ensuite, nous pouvons donner une limite thêta (Θ) - notre fonction fonctionnera pendant ce temps, quelle que soit l'entrée que nous lui donnons.

En général, nous voulons toujours donner une borne thêta si possible car c'est la borne la plus précise et la plus étroite. Si nous ne pouvons pas donner une borne thêta, la meilleure chose suivante est la borne O la plus étroite possible.

Prenons, par exemple, une fonction qui recherche dans un tableau la valeur 0:

def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false
  1. Quel est le meilleur cas? Eh bien, si le tableau que nous lui donnons a 0 comme première valeur, cela prendra un temps constant: Ω (1)
  2. Quel est le pire des cas? Si le tableau ne contient pas 0, nous aurons parcouru tout le tableau: O (n)

Nous lui avons donné une liaison oméga et O, alors qu'en est-il du thêta? On ne peut pas lui en donner un! En fonction du tableau que nous lui donnons, le runtime sera quelque part entre constant et linéaire.

Changeons un peu notre code.

def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)

Pouvez-vous penser au meilleur et au pire des cas? Je ne peux pas! Quel que soit le tableau que nous lui donnons, nous devons parcourir chaque valeur du tableau. Ainsi, la fonction prendra AU MOINS n temps (Ω (n)), mais nous savons également que cela ne prendra pas plus de n temps (O (n)). Qu'est-ce que ça veut dire? Notre fonction prendra exactement n temps: Θ (n).

Si les limites sont déroutantes, pensez-y comme ceci. Nous avons 2 nombres, x et y. On nous donne que x <= y et que y <= x. Si x est inférieur ou égal à y et y est inférieur ou égal à x, alors x doit être égal à y!

Si vous êtes familier avec les listes chaînées, testez-vous et pensez aux durées d'exécution de chacune de ces fonctions!

  1. avoir
  2. retirer
  3. ajouter

Les choses deviennent encore plus intéressantes lorsque vous considérez une liste à double chaînage!

Notation asymptotique

Comment mesurer la valeur de performance des algorithmes?

Considérez que le temps est l'une de nos ressources les plus précieuses. En informatique, nous pouvons mesurer les performances en fonction du temps nécessaire à l'exécution d'un processus. Si les données traitées par deux algorithmes sont les mêmes, nous pouvons décider de la meilleure implémentation pour résoudre un problème.

Nous faisons cela en définissant les limites mathématiques d'un algorithme. Ce sont les notations big-O, big-omega et big-theta, ou les notations asymptotiques d'un algorithme. Sur un graphe, le big-O serait le plus long qu'un algorithme pourrait prendre pour un ensemble de données donné, ou la «borne supérieure». Big-oméga est comme l'opposé de big-O, la «borne inférieure». C'est là que l'algorithme atteint sa vitesse maximale pour n'importe quel ensemble de données. Le grand thêta est soit la valeur de performance exacte de l'algorithme, soit une plage utile entre des limites supérieures et inférieures étroites.

Quelques exemples:

  • "La livraison sera là de votre vivant." (big-O, borne supérieure)
  • «Je peux vous payer au moins un dollar.» (big-oméga, limite inférieure)
  • «Le maximum d'aujourd'hui sera de 25 ° C et le minimum de 19 ° C. (grand-thêta, étroit)
  • «C'est à un kilomètre de marche de la plage.» (gros-thêta, exact)

Plus d'information:

//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-notation-represent //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/