1) Je pense que celui-ci est O (n). p> 2) p> int currentMinIndex = 0;
for (int front = 0; front < intArray.length; front++)
{
currentMinIndex = front;
for (int i = front; i < intArray.length; i++)
{
if (intArray[i] < intArray[currentMinIndex])
{
currentMinIndex = i;
}
}
int tmp = intArray[front];
intArray[front] = intArray[currentMinIndex];
intArray[currentMinIndex] = tmp;
}
3 Réponses :
plus ou moins, oui.
1 est correct - il semble que vous recherchiez un élément spécifique dans ce que je suppose est une collection non triée. Si tel est le cas, le pire des cas est que l'élément est à la toute fin de la liste, donc O (n).
2 est correct, bien qu'un peu étrange. C'est O (1) en supposant que 3 Je crois que cela est considéré comme o (n ^ 2) encore. Il y aurait un facteur constant comme K * N ^ 2, déposer la constante et vous avez obtenu O (n ^ 2).
4 ressemble beaucoup à un algorithme de recherche binaire pour une collection triée. O (logn) est correct. C'est un journal car à chaque itération, vous êtes essentiellement de moitié le nombre de choix possibles dans lesquels l'élément que vous recherchez pourrait être dans.
5 ressemble à un tri bulle, O (n ^ 2), pour des raisons similaires à 3. r et C sont des constantes et les limites ne sont pas des variables. S'ils sont constants, alors oui O (1) car il n'y a rien à saisir.
Pouvez-vous s'il vous plaît voir le point 3, peut-il être O (n ^ 2). Besoin de doute que la boucle intérieure de Coz va itéralement à 0,5 fois la boucle extérieure, ce n'est donc pas complètement O (n ^ 2).
@Punithraj, pour le point 3 - si vous envisagez une boucle extérieure sous forme de o (n) et une boucle interne comme O (N / 2). Ensuite, nous devrions le considérer comme o (n ^ 2). Selon Big O O (N / 2), est O (N). Parce que N / 2 augmente linéairement sur la base de l'entrée 'n'. Par exemple. Si n = 100 alors n / 2 = 50. Si N = 10000, N / 2 = 5000, etc.
o () ne veut rien dire en soi: vous devez spécifier si vous comptez le "pire cas" O, ou le cas moyen O. pour un algorithme de tri, ils ont un O (n log n ) en moyenne mais une o (n ^ 2) dans le pire des cas.
Fondamentalement, vous devez compter le nombre total d'itérations de la plus grande boucle interne et prendre la plus grande composante du résultat sans aucune constante (par exemple si vous avez K * (K + 1) / 2 = 1/2 K ^ 2 + 1/2 k, le plus gros composant est 1/2 k ^ 2 donc vous êtes O (k ^ 2)).
Par exemple, votre élément 4) est dans O (journal (n)) car, si vous travaillez sur une matrice de taille N, vous exécuterez une itération sur ce tableau, et la suivante sera sur un tableau de taille n / 2, puis n / 4, ..., jusqu'à ce que cette taille atteigne 1. Donc, il s'agit de log (n) itérations.
Non, il y a thêta et .. quelque chose d'autre pour le meilleur et le cas moyen. Big O est toujours le pire des cas.
Convenu de la notation thêta, bien que beaucoup de gens utilisent O pour une affaire moyenne; On dit souvent une trace rapide pour être O (n log n) ...
Votre question concerne principalement la définition de O ().
Quand quelqu'un dit que cet algorithme est O (log (n)), vous devez lire:
Lorsque le paramètre d'entrée N devient très gros, le nombre d'opérations effectuées par l'algorithme grandit au plus dans le journal (n)
Maintenant, cela signifie deux choses:
Alors gardez cela à l'esprit, retour à vos problèmes:
n est myarray.length et le nombre d'opérations que vous comptez est "==". Dans ce cas, la réponse est exactement n, qui est O (n)
Vous ne pouvez pas spécifier N
Le n ne peut être que k et le nombre d'opérations que vous comptez est de ++. Vous avez exactement k * (k + 1) / 2 qui est O (n2) comme vous dites
Cette fois-NE N est à nouveau la longueur de votre matrice et l'opération que vous comptez est ==. Dans ce cas, le nombre d'opérations dépend des données, nous parlons généralement de «pire des scénarios», ce qui signifie que de tout le résultat possible, nous examinons celui qui prend le plus de temps. Au mieux, l'algorithme prend une comparaison. Pour le pire des cas, prenons un exemple. Si le tableau est [[1,2,3,4,5,6,7,8,9]] et vous recherchez 4, votre intarray [MID] deviendra successivement, 5, 3, puis 4, et ainsi Vous auriez fait la comparaison 3 fois. En fait, pour un tableau de la taille de 2 ^ K + 1, le nombre maximal de comparaison est K (vous pouvez vérifier). Donc n = 2 ^ k + 1 => k = ln (n-1) / ln (2). Vous pouvez étendre ce résultat au cas lorsque N n'est pas = 2 ^ k + 1, et vous obtiendrez la complexité = O (ln (n))
Dans tous les cas, je pense que vous êtes confus parce que vous ne savez pas exactement ce que O (n) signifie. J'espère que c'est un début.
3) est O (k ^ 2) parce que vous ferez K * (k + 1) / 2 ops, qui est O (K ^ 2). 5) est la même chose: la boucle interne exécute N, puis n-1, puis N-2 ... puis 1 fois, donc globalement N * (n + 1) / 2 fois, donc O (n ^ 2).
5) est le tri de la bulle ( en.wikipedia.org/wiki/bubble_sort ), qui est o (n ^ 2).
Peux-tu élaborer? La boucle interne ne fonctionne-t-elle pas N * (N + 1) / 2 fois? Et la boucle extérieure ne fonctionne-t-elle pas N fois. Alors n'est-ce pas que [n * (n * (n + 1) / 2)]]
@ordinaire: Vérifiez ma réponse, quelle importance est le nombre de fois que vous effectuez la comparaison, ce n'est donc que le nombre total de fois que la boucle interne est exécutée, à savoir N * (N + 1) / 2