Revision history [back]
 | 1 | initial version | posted 2014-12-09 20:09:49 +0100  |
Insert O(1) && ExtractMedian O(1)
V zadání je: "Dokažte, že nemůže existovat datová struktura, která má operace Insert a ExtractMedian, jejichž složitost je v nejhorším případě O(1)." Stačilo by říct, že extractMedian lze provést v O(1) jen v poli, které je vždy seřazené a při vkládání je tedy potřeba všechny prvky posunou v O(n) čase? Nebo jak to říct lépe?
Insert O(1) && ExtractMedian O(1)
V zadání je: "Dokažte, že nemůže existovat datová struktura, která má operace Insert a ExtractMedian, jejichž složitost je v nejhorším případě O(1)." Stačilo by říct, že extractMedian lze provést v O(1) jen v poli, které je vždy seřazené a při vkládání je tedy potřeba všechny prvky posunou v O(n) čase? Nebo jak to říct lépe?
