Revision history [back]
 | 1 | initial version | posted Dec 9 '14  |
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?
| | 2 | retagged |
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?
