Error: (8192) Creation of dynamic property App\Layout\Layouts\Base\Base::$viewFile is deprecated

Quiz Complexité des tas et arbres binaires

Quelle est la complexité de la fonction suivante en fonction de la taille N du vector v ?

void f(const vector<int>& v)
{
   const size_t N = v.size();
   push_heap(v.begin(), v.end());
}
O(log2(N))

Quelle est la complexité (dans le pire cas) de la fonction suivante en fonction de la taille N du vector v ?

void f(const vector<int>& v)
{
   const size_t N = v.size();
   set<int> s(v.begin(), v.end());
   cout << s.size();
}
O(N * log2(N))

Quelle est la complexité de la fonction suivante en fonction de la taille N du vector v ? On suppose N très grand.

void f(const vector<char>& v)
{
   const size_t N = v.size();
   set<char> s(v.begin(), v.end());
   cout << s.size();
}
O(N)
O(N * log(N)) s'approche de O(N) pour N très grand. C'est piégeux on aurra pas ça à l'exa.

Quelle est la complexité de la fonction suivante en fonction de la taille N du vector v ?

void f(const vector<int>& v)
{
   const size_t N = v.size();
   priority_queue<int> pq;
   for (auto i : v)
      pq.push(i);

   while (not pq.empty())
   {
      cout << pq.top();
      pq.pop();
   }
}
O(N * log2(N))

Quelle est la complexité de la fonction suivante en fonction de la taille N du vector v ?

void f(const vector<int>& v)
{
   const size_t N = v.size();
   make_heap(v.begin(), v.end());
}
O(N)

Quelle est la complexité de la fonction suivante en fonction de la taille N du vector v ? On a préalablement appelé make_heap(v.begin(), v.end() - 1);

void f(const vector<int>& v)
{
   const size_t N = v.size();
   for (size_t i = 0; i < N; ++i)
      push_heap(v.begin(), v.end());
}
O(N)

Quelle est la complexité de la fonction suivante en fonction de la taille N du vector v ? On a préalablement appelé make_heap(v.begin(), v.end() - 1);

void f(const vector<int>& v)
{
   const size_t N = v.size();
   for(size_t i = 1; i < N; i *= 2)
      push_heap(v.begin(), v.end());
}
O(log2(N))