L'algorithme de la complexité du temps de la suppression dans un tableau non trié
Suppose qu'il y a des ménagères de matrice A, et il contient un élément x (x est le pointeur de l'élément), et chaque élément a un satellite de la variable k. Ainsi, nous pouvons obtenir le temps suivant la complexité (pour le pire des cas):
Si nous voulons de Recherche pour un certain K, alors il en coûte O(n).
si nous voulons Insérer un élément, puis il en coûte O(1), parce qu'Un juste ajoute l'élément à la fin.
Que si nous savons x, puis Supprimer à partir de la matrice A?
Nous avons à de Recherche pour x.k première et d'obtenir l'indice de x, alors Supprimer x via son index dans Un, droit?
Donc pour Supprimer, il en coûte O(n) trop, non?
grâce
OriginalL'auteur Jackson Tale | 2012-02-20
Vous devez vous connecter pour publier un commentaire.
Trouver l'élément avec une valeur donnée est linéaire.
Depuis le tableau n'est pas trié de toute façon, vous pouvez faire la suppression elle-même en temps constant. Premier swap, l'élément que vous souhaitez supprimer à la fin de la rangée, puis réduire la taille de la matrice par un seul élément.
Ce serait encore triées -- tout simplement pas dans l'ordre croissant (ou décroissant).
Je pense que les auteurs normalement la distinction entre "ordonné" et "triés". Un "triés" tableau est précisément celui dans lequel l'ordre dépend de la valeur des objets qu'il contient. Un tableau qui a été commandé par insérez-le temps n'est pas habituellement décrit comme "triés", même lorsqu'il est important que l'insert de temps de l'ordre est conservé.
Cela dit, l'interlocuteur appelle la matrice de "non triés" sans plus de commentaire, donc je pense qu'il est juste de supposer que l'ordre est sans importance jusqu'à preuve du contraire.
est-ce la façon dont il est normalement mis en œuvre? c'est, d'échanger un élément non trié arr à la fin et réduire?
OriginalL'auteur Jerry Coffin
Oui, c'est vrai. Aussi, si c'est un tableau, la suppression de la seule volonté de prendre
O(n)
temps car après vous supprimez l'élément, vous aurez besoin de déplacer tous les éléments à droite de cet élément d'une position vers la gauche. Donc, même si vous savez que x (par exemple, vous n'aurez qu'à supprimer le premier élément), il faudraO(n)
temps.OriginalL'auteur Sabbir Yousuf Sanny
Oui. Il faut
O(n)
de temps pour trouver l'élément que vous souhaitez supprimer. Puis dans afin de le supprimer, vous devez déclarer tous les éléments d'un espace vers la gauche. C'est aussiO(n)
de sorte que le total de la complexité est linéaire.Aussi, si vous parlez de la statique des tableaux, insérer prend
O(n)
. Vous avez pour redimensionner le tableau, afin d'accueillir l'élément supplémentaire. Il existe des moyens pour amortir ce temps d'exécution deO(1)
.OriginalL'auteur tskuzzy