1
votes

en utilisant set pour trier dans le journal (N)?

La complexité temporelle de tout le code est-elle O (log (N))? (En amorti). Et si, peut-on utiliser cette méthode de tri à chaque fois? Au départ, il était nécessaire de trier certains nombres.

#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 

    int numbers[]={60 , 2 , 3 , 35, 67, 111, 5, 7};
    set<int> s (numbers,numbers+8);
    for(auto x : s)
    {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

c++ data-structures

3 commentaires

#include en utilisant l'espace de noms std; Veuillez arrêter de faire ça.

Astuce: std :: begin et std :: end vous donnent des itérateurs pour les tableaux: set s (std :: begin (numbers), std: : end (nombres)); Il évite les nombres magiques ( +8 ici) ou le calcul de la taille vous-même (comme sizeof (nombres) / sizeof (* nombres) ).

Techniquement pas de complexité. Le code ne compile pas: godbolt.org/z/Q0XvCy

4 Réponses :

2
votes

À proprement parler, la complexité de votre code dans son ensemble est constante. Il n'y a pas de n que vous pourriez augmenter pour observer une durée d'exécution accrue.

Je suppose que ce à quoi vous vous référez en fait est: Trier n entiers via la construction d'un std :: set . Dans ce cas, vous devez considérer que la complexité de ce constructeur est O (n log (n)) (si l'entrée n'est pas déjà triée, voir par exemple ici . Comparez cela au tri d'un std :: vector (ou d'un autre conteneur) via std :: sort , qui est O (n log (n)) également, vous ne gagnez pas ici en utilisant un std :: set .

0 commentaires

4
votes

La complexité temporelle de tout le code est-elle O (log (N))?

Non, ce n'est pas le cas.
set<int> s;
s.insert(60);

...

s.insert(7);
est un raccourci pour:
set<int> s {60 , 2 , 3 , 35, 67, 111, 5, 7};
La complexité de chaque insérer est O (log (size ())) . Depuis https://en.cppreference.com/w/cpp/container/set / insert :

Complexité
1-2) Logarithmique de la taille du conteneur, O (log (size ())).

La complexité de toute l'opération est O (N * log (N)) .

0 commentaires

8
votes

Selon [set.cons] \ 4 les constructeurs d'itérateur de std :: set a un

Complexité: Linéaire en N si la plage [first, last) est déjà triée en utilisant comp et sinon N log N , où N est dernier - premier .

Donc, dans votre cas, vous avez toujours une complexité de N log N car les nombres ne sont pas triés et ce n'est pas différent d'utiliser simplement std: : triez comme

int main() 
{ 

    int numbers[]={60 , 2 , 3 , 35, 67, 111, 5, 7};
    std::sort(std::begin(numbers), std::end(numbers));
    for(auto x : numbers)
    {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

sauf que dans le cas de l'utilisation d'un ensemble, vous devez allouer des nœuds pour que vous ayez tout ce coût ajouté.

0 commentaires

2
votes

La complexité temporelle est log (n), où n = aucun élément dans l'ensemble, pour chaque opération d'insertion. Donc, pour insérer tous les éléments, la complexité temporelle globale serait nlog (n) sauf si vous spécifiez explicitement la position optimale pour insérer l'élément, alors dans ce cas, il sera amorti constant.

0 commentaires