Здравствуйте такой код

std::vector<Object> obj_;
...............................
for(size_t i = 0, sz = obj_.size() - 1; i < sz; ++i)
{
...............................
 sort(obj_.begin() + i, obj_.end()); // Пускай это не   quick  сорт, а слиянием и всегда выполняетьс за NlogN
.............................
}

Я так понимаю это можно выразить рядом NlogN + (N -1 )log (N — 1) + (N — 2 )log (N — 2) + (N — 3 )log (N — 3) .... можно ли это выразить как то одной формулой.

А>Я так понимаю это можно выразить рядом NlogN + (N -1 )log (N — 1) + (N — 2 )log (N — 2) + (N — 3 )log (N — 3) .... можно ли это выразить как то одной формулой.

O(logN * N^2)

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте такой код


А>

А>std::vector<Object> obj_;
А>...............................
А>for(size_t i = 0, sz = obj_.size() - 1; i < sz; ++i)
А>{
А>...............................
А> sort(obj_.begin() + i, obj_.end()); // Пускай это не   quick  сорт, а слиянием и всегда выполняетьс за NlogN
А>.............................
А>}
А>

А>Я так понимаю это можно выразить рядом NlogN + (N -1 )log (N — 1) + (N — 2 )log (N — 2) + (N — 3 )log (N — 3) .... можно ли это выразить как то одной формулой.

А что? Уже вывели формулу определения сложности? И которая уже есть во всех учебниках?

Не знал

Ну и вывод асимптотики ряда, для полноты ответа:
n/2 log(n)+ n/2 log(n-1) +...<n log(n)+(n-1)log(n-1)+...<n log(n)+ n log(n-1)+...
или
n/2 log(n!)<n log(n)+(n-1)log(n-1)+...<n log(n!)
и далее по формуле Стирлинга log(n!) ~ O(n log(n))

А потом сложность разная бывает...

1) Командная цикломатическая (алгоритмическая, графовая) сложность
2) Сложность чтения/восприятия/понимания
3) Сложность внесения изменений (модификации)
4) Сложность отладки/тестирования/поиска ошибок
5) Семиотическая сложность (когда идентификаторы лексемы используются в разных
конструкциях с разной семантикой, т.е. когда трудно за 1 просмотр выделить
глазами все использования цепочки символов и приходится просматривать
участок кода по много раз, чтобы понять его назначение).
6) Количественная сложность (определяется объёмом кода)

Есть другие

(с)

Здравствуйте, Доктор ТуамОсес, Вы писали:

ДТ>А что? Уже вывели формулу определения сложности? И которая уже есть во всех учебниках?

Ну и зачем придираться к словам ?
В случаях с сортировками обычно под сложностью понимают число сравнений элементов. Вообще, в случаях с алгоритмами под сложностью обычно понимают число шагов некоторой абстрактной машины (например машины Тьюринга) реализующей данный алгоритм.

Здравствуйте, dilmah, Вы писали:
А>>Я так понимаю это можно выразить рядом NlogN + (N -1 )log (N — 1) + (N — 2 )log (N — 2) + (N — 3 )log (N — 3) .... можно ли это выразить как то одной формулой.
D>O(logN * N^2)
может легко так получиться что будет быстрее — или как n*n или вообще как n. амортизационный анализ или как там его. зависит от того, насколько сильно элементы будут перемешаны и от реализации сортировки