Здравствуйте, Кодт, Вы писали:
К>Кажется, ответ. На С++.
К>К>nth_element(a.begin(), a.begin()+k1, a.end()); // O(N)
К>nth_element( a.begin()+k1, a.begin()+k2, a.end()); // O(N-k1)
К>sort ( a.begin()+k1, a.begin()+k2 ); // O(K*log(K))
К>
а это не гарантирует, что между к1 и к1 окажутся именно нужные значения, нужно ведь чтобы для i<k1: a[i]<=a[k1] && i>k2: a[i]>=a[k1]
Здравствуйте, Кодт, Вы писали:
К>Кажется, ответ. На С++.
К>К>nth_element(a.begin(), a.begin()+k1, a.end()); // O(N)
К>nth_element( a.begin()+k1, a.begin()+k2, a.end()); // O(N-k1)
К>sort ( a.begin()+k1, a.begin()+k2 ); // O(K*log(K))
К>
Ага, у nth_element есть хорошее свойство
After nth_element the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted. Also for any iterator i in the range [first, nth) and any iterator j in the range [nth, last) it holds that: !(*i > *j) or comp(*j, *i) == false.
Только вот сложность этой штуки только в среднем O(N)+O(KlogK). А в худшем зависит от реализации STL, по стандарту то никаких ограничений на сложность в худшем случае нет
.
И если std::sort в популярных реализациях STL имеет в худшем случае сложность O(nlogn), то вот найти реализацию, где std::nth_element имеет в худшем случае сложность O(n), будет сложновато.
... << RSDN@Home 1.1.4 beta 7 rev. 447>>
Здравствуйте, Аноним, Вы писали:
PD>>Можно ли получить этот отрезок за время Klog(K) , т.е без сортировки всего массива ?
А>Можно.
Вне зависимости от N?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Перекуём баги на фичи!
