From b37e0e5e7ece77a3ea5d9867c2d6a18359a43ef7 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 16 May 2007 15:07:27 +0200 Subject: [PATCH] Opravena chyba v definici medianu, nerovnost ma byt neostra. --- 3-strassen/3-strassen.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/3-strassen/3-strassen.tex b/3-strassen/3-strassen.tex index 4b38463..b8abdea 100644 --- a/3-strassen/3-strassen.tex +++ b/3-strassen/3-strassen.tex @@ -103,7 +103,7 @@ Zat V tomto oddílu se budeme zabývat tím, jak co nejrychleji najít v jakékoli posloupnosti $n$ èísel $k$-tý nejmen¹í prvek popøípadì medián. Pro ty, kdo medián neznají, tu máme definici: \s{Definice:} -Medián posloupnosti $a_1, a_2,\ldots , a_n$ je takové $m=a_i$, kde ménì ne¾ $n/2$ prvkù je men¹ích ne¾ $m$ a ménì ne¾ $n/2$ prvkù je vìt¹ích ne¾ $m$. +Medián posloupnosti $a_1, a_2,\ldots , a_n$ je takové $m=a_i$, kde nejvý¹e $n/2$ prvkù je men¹ích ne¾ $m$ a nejvý¹e $n/2$ prvkù je vìt¹ích ne¾ $m$. Nejjednodu¹¹ím øe¹ením by urèitì bylo celou posloupnost nejdøíve setøídit a pak u¾ jednodu¹e vyhmátnout po¾adovaný prvek. To bychom dokázali v celkem slu¹ném èase $\O(n\log n)$, ale u¾ teï mù¾eme prozradit, ¾e to jde v èase $\O(n)$. Jak? -- 2.39.2