J'ai ce code qui renvoie le carré d'un tableau dans l'ordre trié et j'essaie de déterminer sa complexité de temps. Je fais une boucle à travers les données ( o (n) ), puis utilisez la troisième série ( O (n journal n) ). Je suppose que cela signifie que je fais n * n journal n travail, donc c'est n ^ 2 complexité. Mais lorsque j'ai vérifié une réponse pour cette question, la complexité temporelle de cette fonction est apparemment juste juste n log n . Pourquoi est-ce?
3 Réponses :
Votre première pour la boucle est prise Donc, globalement, votre complexité de temps sera Lorsque nous excluons les limites inférieures tout en calculant la complexité de temps, votre complexité de temps globale sera donc O (n) la complexité de temps et la tresse de fusion prend o (nlogn)
t (n) = O (n) + o (nlogn)
O (nlogn)
Une boucle prends votre Votre complexité totale sera donc O (n) + (N log n)) Code> Mais il suffit de ne pas concerner la plus grande valeur de sorte que votre complexité de temps sera Si vous faites comme ceci: p> O (n) code>, puis vous faites le MERGEORT (O (n journal n)) code> (O (n log n)) code> public int[] sortedSquares(int[] A) {
for(int i = 0; i < A.length; i++) {
A[i] = A[i] * A[i];
mergeSort(A);
}
return A;
}
public int[] sortedSquares(int[] A) {
for(int i = 0; i < A.length; i++) {
A[i] = A[i] * A[i];
}
mergeSort(A);
return A;
}
Time Complexity: O(N) + O(N log N) = O(N log N)
Explanation:
Firstly you have traversed the array so it takes O(N) time. After the traversing the array you have applied merge sort which takes O(N log N). But we have considered the higher complexity so your time complexity is O(N log N).
O (n) + (O (n) = O (2n) = O (n) . Maintenant, vous avez toujours le facteurlog N , mais le même principe s'applique .C'est comme si votre boucle de boucle prend O (n) et Mergesort prend O (nlogn) et puisque la tresse de fusion n'est pas à l'intérieur de la boucle, elle ne fonctionnera qu'une seule fois. La complexité de temps résultante sera donc O (n) + O (nlogn) I.e. O (nlogn) . J'espère que cela vous aidera.