Pour la deuxième durée que je donne en exemple, j'imagine qu'osef de la partie "3n²+2" ?
Pseudo supprimé26 janvier 2021 à 00:43:34
n^O(1) c'est juste une façon rapide de dire "n^x pour une certaine constante x" ?
Message édité le 26 janvier 2021 à 00:44:05 par Pseudo supprimé
TheLelouch4
Niveau 69
26 janvier 2021 à 00:47:32
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
Pseudo supprimé26 janvier 2021 à 00:47:44
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 ?
Message édité le 26 janvier 2021 à 00:48:08 par Pseudo supprimé
Pseudo supprimé26 janvier 2021 à 00:49:08
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" ?
dropthezitounes
Niveau 10
26 janvier 2021 à 00:51:00
Bah C'est pas juste non ? O(1) ça veut pas dire que l'exposant est pas plus grand que 1 ?
Pseudo supprimé26 janvier 2021 à 00:53:37
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
Message édité le 26 janvier 2021 à 00:53:51 par Pseudo supprimé
dropthezitounes
Niveau 10
26 janvier 2021 à 00:57:32
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
Pseudo supprimé26 janvier 2021 à 00:59:55
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 ?
Message édité le 26 janvier 2021 à 01:01:11 par Pseudo supprimé
Pseudo supprimé26 janvier 2021 à 01:04:46
Je ne pensais pas poser une colle au forum
HappyAubrey
Niveau 55
26 janvier 2021 à 01:06:25
Première fois que je vois un grand O en exposant.
dropthezitounes
Niveau 10
26 janvier 2021 à 01:08:08
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 ?
AR7CORE
Niveau 5
26 janvier 2021 à 01:08:31
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.
Pseudo supprimé26 janvier 2021 à 01:09:52
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" ?
Pseudo supprimé26 janvier 2021 à 01:10:37
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
Message édité le 26 janvier 2021 à 01:11:03 par Pseudo supprimé
ComteMonte
Niveau 9
26 janvier 2021 à 01:10:48
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
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
AR7CORE
Niveau 5
26 janvier 2021 à 01:11:56
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 ?
Flo318
Niveau 10
26 janvier 2021 à 01:12:52
C'est une notation de complexité algorithmique je crois bien