La complexité temporelle de la recherche binaire pour un tableau non trié

Je suis coincé avec deux temps de complexités. Pour faire une recherche binaire avec tableau trié est O(logN). Donc à la recherche d'un tableau non trié, nous devons d'abord afin que devient O(NlogN). Alors, nous pouvons effectuer une recherche binaire qui donne la complexité en O(N) mais j'ai lu que cela pouvait être en O(NlogN). Ce qui est correct?

source d'informationauteur user1521306

  1. 22

    Binaire de la Recherche pour "Trié" les listes. La complexité est en O(logn).

    Binaire de Recherche ne fonctionne pas pour les "non-Tri" des listes. Pour ces listes, il suffit de faire droit recherche en commençant par le premier élément, ce qui donne une complexité de O(n). Si vous étiez à trier le tableau avec MergeSort ou de toute autre O(nlogn) algorithme de la complexité serait en O(nlogn).

    O(logn) < O(n) < O(nlogn)

  2. 2

    La réponse à votre question est dans votre question elle-même. Vous êtes le premier tri de la liste. Si vous triez votre liste à l'aide de quick ou de fusion de tri, la complexité devient o(nlog n). Partie - 1 devient de plus. Deuxième partie de l'exécution d'un binaire de recherche est effectuée sur la 'liste'. La complexité binaire de recherche est o(log n). Donc en fin de compte de la complexité du programme reste en o(nlog n). Cependant, si vous souhaitez calculer la médiane du tableau, vous n'avez pas à trier la liste. Une simple application d'un linéaire ou séquentiel, la recherche peut vous aider avec ça.

  3. 0

    La complexité du temps de la recherche linéaire est O(n) et de recherche binaire est O(log n) (log en base 2). Si nous avons un tableau non-trié et que vous voulez utiliser la recherche binaire pour cela, nous avons pour trier le tableau en premier. Et ici nous avons à passer un temps O(n logn) pour trier le tableau et ensuite passer du temps à la recherche de l'élément.