2^k * n^O(1).
(" 2 puissance k, multiplié par n puissance grand O de 1").

Je ne suis pas vraiment à l'aise avec les notations grand O
Par exemple, parmi les durées suivantes d'algorithmes, lesquelles sont en 2^k * n^O(1) ?

1) durée 2^k * n^5
2) durée 2^k * (n^3+3n^2+2)
3) durée 2^k * 6n^12

Pour la deuxième durée que je donne en exemple, j'imagine qu'osef de la partie "3n²+2" ?

n^O(1) c'est juste une façon rapide de dire "n^x pour une certaine constante x" ?

O(1) c'est juste une quantité bornée qui est indépendante de n, pour dire que c'est un truc constant en le nombre d'opérations

La différence entre 2^k * n^O(1) et O( 2^k *polynome(n) ) c'est quoi ? C'est juste que dans la deuxième notation, le polynôme n'est pas forcément unitaire ?

Le 26 janvier 2021 à 00:47:32 TheLelouch4 a écrit :
O(1) c'est juste une quantité bornée qui est indépendante de n, pour dire que c'est un truc constant en le nombre d'opérations

Ok merci pour la réponse!
Donc ça peut vraiment se lire "n puissance x pour une certaine constante x" ?

Bah C'est pas juste non ? O(1) ça veut pas dire que l'exposant est pas plus grand que 1 ?

Le 26 janvier 2021 à 00:51:00 dropthezitounes a écrit :
Bah C'est pas juste non ? O(1) ça veut pas dire que l'exposant est pas plus grand que 1 ?

Hein ?
Tu serais pas en train de me faire un mix avec la notation "petit o" ?
Autant j'ai du mal à comprendre les notations grand O, autant non je ne pense pas que ça veut dire ce que tu dis

Le 26 janvier 2021 à 00:53:37 Questiondinfo a écrit :

Le 26 janvier 2021 à 00:51:00 dropthezitounes a écrit :
Bah C'est pas juste non ? O(1) ça veut pas dire que l'exposant est pas plus grand que 1 ?

Hein ?
Tu serais pas en train de me faire un mix avec la notation "petit o" ?
Autant j'ai du mal à comprendre les notations grand O, autant non je ne pense pas que ça veut dire ce que tu dis

Bah grand O C'est pour déterminer la complexité maximale il me semble

En gros :

J'ai un exo qui me demande de créer un algorithme pour résoudre un certain problème en temps 2^k * n^O(1).
Dans le cours, on a vu un algorithme qui permet de résoudre ce problème en temps O(2^k * polynome(n) ).

Les questions que je me pose :
L'algorithme vu en cours convient-il ? Si non, pourquoi ?

Ma réponse :
-Il ne convient pas forcément, ça dépend de la valeur de ce "polynome(n)". Si le polynôme est unitaire ça convient, sinon non

Est-ce que je viens de dire une bêtise ?

Je ne pensais pas poser une colle au forum

Première fois que je vois un grand O en exposant.

N est effectivement un polynôme et ça conviendrait. Mais ils ont pas définie la fonction polynôme ? Parce que ça pourrait être un autre polynôme
?

O(1) = complexité constante, ton algo doit être aussi rapide quel que soit l'entrée, et 2^k c'est que pour k entrées, ton algo doit faire au maximum 2^k opérations, genre un tri de tableau.

Le 26 janvier 2021 à 01:08:31 AR7CORE a écrit :
O(1) = complexité constante, ton algo doit être aussi rapide quel que soit l'entrée, et 2^k c'est que pour k entrées, ton algo doit faire au maximum 2^k opérations, genre un tri de tableau.

Donc n^O(1) ça peut se lire "n^x avec x une constante" ?

Le 26 janvier 2021 à 01:08:08 dropthezitounes a écrit :
N est effectivement un polynôme et ça conviendrait. Mais ils ont pas définie la fonction polynôme ? Parce que ça pourrait être un autre polynôme
?

Je ne comprends rien à tes messages, je vais supposer que tu trolles

Putain merde je me souviens plus comment ça s'appelle

C'est si tu veux l'exactitude de la limite à ce moment là tu remplaces
Par contre tu trouveras pas sur internet, regarde bien dans les exos avec le prof

Le seul truc en maths où pour sa documentation n'existe pas vraiment

https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation

Le 26 janvier 2021 à 01:10:37 Questiondinfo a écrit :

Le 26 janvier 2021 à 01:08:08 dropthezitounes a écrit :
N est effectivement un polynôme et ça conviendrait. Mais ils ont pas définie la fonction polynôme ? Parce que ça pourrait être un autre polynôme
?

Je ne comprends rien à tes messages, je vais supposer que tu trolles

Non

Le n^O(1) perso je le lis comme "pour chaque n", juste un truc de liaison, mais je peux me tromper
L'algo doit faire quoi ?

C'est une notation de complexité algorithmique je crois bien