используя набор для сортировки в журнале (N)?

Question

Временная сложность всего кода O (log (N))? (Амортизируется). И если, поэтому мы можем использовать этот метод для сортировки, каждый раз? Изначально нужно было отсортировать некоторые числа.

#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;
}

Answer 1

Per [set.cons] \ 4 конструкторы итераторов std::set имеют

Сложность: Линейный в N, если диапазон [first, last) уже отсортирован с использованием comp, а в противном случае N log N, где N равно last - first.

Так что в вашем случае у вас все еще есть сложность N log N, поскольку numbers не сортируется и ничем не отличается от простого использования std::sort, как

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;
}

за исключением того, что в случае использования набора вам нужно выделить узлы, чтобы вы добавили все эти затраты.

Answer 2

Является ли сложность по времени всего кода O (log (N))?

Нет, это не так.

set<int> s {60 , 2 , 3 , 35, 67, 111, 5, 7};

- это сокращение для:

set<int> s;
s.insert(60);

...

s.insert(7);

Сложность каждого insert равна O(log(size())).От https://en.cppreference.com/w/cpp/container/set/insert:

Сложность
1-2) Логарифмический размер контейнера, O (log (size ())).

Сложность всей операции O(N * log(N)).

Answer 3

Сложность по времени составляет log (n), где n = нет элементов в наборе, для каждой операции вставки. Таким образом, для вставки всех элементов общая сложность по времени будет равна nlog (n), если вы явно не укажете оптимальную позицию для вставки элемента, тогда в этом случае она будет амортизированной постоянной.

Answer 4

Строго говоря, сложность вашего кода в целом постоянна. Нет n, которое вы могли бы увеличить, чтобы наблюдать увеличение времени выполнения.

Я предполагаю, что вы на самом деле имеете в виду: сортировка n целых чисел путем построения std::set. В этом случае вы должны учитывать, что сложность этого конструктора составляет O (n log (n)) (если входные данные еще не отсортированы, см., Например, здесь . Сравните это с сортировкой std::vector ( или некоторый другой контейнер) через std::sort, что также является O (n log (n)), вы не получите здесь, используя std::set.