П1∝П2 (за символа потърсете "\propto" в Google Images) трудна ~> неизвестна "Ако П2 се решаваше бързо, то и П1 щеше да се решава бързо" Обратното, ако П1 се решава "бавно", то и П2 трябва да се решава "бавно" - известно "трудни" (бавни) = Omega(nlgn) - Сортиране на масив - Element Uniqueness (EU) - Minimal Distance (MinDist) ? Closest Pair (Minimal Distance in 2D) ? Minimal Distance in 3D (MinDist3D) --- Доказателство за долна граница на Mode --- --- Редукция Element Uniqueness ~> Mode --- EU ~> Mode EU(A[1..n] : array of integers) 1. m <- Mode(A[1..n]) 2. if Count(m,A[1..n]) = 1 3. return Yes 4. else 5. return No Доказателство за коректност на редукцията: Нека m е резултатът, който връща алгоритъмът Mode, т.е. някой най-често срещан елемент в масива (може да не е уникален). Тъй като Mode работи коректно, то не съществува елемент в масива, който се среща в него повече пъти (иначе - противоречие с коректността му). Ако броя срещания на този най-често срещан елемент в масива е 1, то не съществува елемент, който да се среща повече пъти => всички елементи в масива са уникални. Тогава отговорът на задачата EU трябва да бъде "Да", и точно това връща алгоритъмът в този случай. Ако този най-често срещан елемент се среща повече от веднъж в масива, то не всички елементи в него са уникални и алгоритъмът ни трябва да върне "Не" - което той прави. Ако времето за изпълнение на Mode е o(nlgn), то времето за изпълнение на EU щеше да е o(nlgn) + O(n) = max{o(nlgn),O(n)} = = o(nlgn). Но е доказано, че EU не може да бъде решена във време o(nlgn) => противоречие => не е възможно и Mode да бъде решавана в o(nlgn) време --- Доказателство за долна граница на Minimal Distance --- --- Редукция Element Uniqueness ~> Minimal Distance --- EU ~> Minimal Distance EU(A[1..n] : array of integers) 1. dist <- MinDist(A[1..n]) 2. if dist = 0 3. return No 4. else 5. return Yes Доказателство за коректност на редукцията: Нека d е резултатът, който MinDist връща, т.е. най-малката разлика между две числа на различни позиции в масива. Ако това минимално разстояние е 0, то в масива съществуват два елемента на различни позиции, които са равни => не всички елементи в масива са уникални. В такъв случай алгоритъмът за EU връща "Не", което е коректния отговор. Ако минималното разстояние е >0, то не съществуват различни елементи в масива, които да са равни помежду си (в противен случай MinDist щеше да върне 0). Тогава под дефиниция всички елементи в масива са уникални и алгоритъмът връща "Да", което отново е коректния отговор. Ако задачата Minimal Distance се решаваше за време o(nlgn), то и EU щеше да работи за o(nlgn) време => противоречие с доказаното на лекции, че EU винаги се решава за Omega(nlgn) време => Minimal Distance също винаги се решава за Omega(nlgn). --- Доказателство за долна граница на Minimal Distance in 3D --- --- Редукция MinDist ~> MinDist3D --- MinDist ~> MinDist3D MinDist(A[1..n]: array of integers) 1. B[1..n]: array of 3D points 2. for i<- 1 to n 3. B[i] <- (A[i],0,0) 4. d <- MinDist3D(B[1..n]) 5. return d Доказателство за коректност на редукцията: по дефиниция MinDist3D ще върне минималното разстояние между някои две точки на различни позиции в масива B, т.е. min{sqrt((xi-xj)^2 + (yi-yj)^2 + (zi-zj)^2) | i!=j}. Тъй като по построение за всяка точка B[i] в масива yi = zi = 0 и xi = A[i], то това минимално разстояние е равно на min{|A[i]-A[j]| | i!=j}. По дефиниция това е именно минималната разлика между два елемента в подадения масив A[1..n], и алгоритъмът MinDist връща точно тази стойност => алгоритъмът работи коректно. Ако задачата MinDist3D се решава за o(nlgn), то и задачата MinDist ще се решава за o(nlgn) + O(n) = max{o(nlgn),O(n)} = o(nlgn) време. Това е в противоречие с доказаната сложност по време на MinDist от Omega(nlgn) => не е възможно MinDist3D да се решава за o(nlgn) и това е теоретичната долна граница - също Omega(nlgn) --- Доказателство за теоретична долна граница на Търсене в сортиран масив --- Задачата "Търсене в сортиран масив" е: при даден сортиран масив A[1..n] и дадено число k да се отговори дали k се съдържа в A[1..n] или не. Докажете, че тази задача има долна граница Omega(lgn), ако търсенето е базирано на директни сравнения, т.е. достъпът до елементите на A[] става единствено чрез сравнения от вида "A[i] равно ли е на k". Решение: Всяко дърво на решения, решаващо тази задача, трябва да разпознава n+1 различни отговора на задачата: k се среща на първата позиция в масива, на втората,..., на n-тата позиция или k не се среща в масива. Всяко листо в дървото трябва да отговаря на един-единствен отговор измежду тях (в противен случай няма да можем да различаваме някои от различните решения и можем да получим некоректен отговор на задачата при някакви входни данни). Тъй като въпросите (query-та), които задаваме, имат само два отговора - "да" и "не", то дървото на решения трябва да бъде двоично. Тогава за двоично дърво с n+1 листа имаме, че височината му в най-добрия случай може да бъде roundup(log2(n+1)) = Theta(lgn). Това означава, че всеки един алгоритъм, решаващ тази задача, ще има дърво на решения с височина поне Theta(lgn), т.е. винаги ще работи за време Omega(lgn). --- Доказателство за долна граница на Задачата за четирите топки с неизвестни тегла --- Тук разсъждението е аналогично на предишната задача, Търсене в сортиран масив. За тази задача възможните решения са 4!=24 (всички възможни пермутации на четирите тегла над четирите топки). Този път въпросите, които задаваме са премервания на теглилката, които имат три възможни отговора - поставените топки на лявото блюдо са по-тежки, поставените обекти на дясното блюдо са по-тежки, или двете блюда се балансират. Забележете, че нямаме опция за въпроси от вида "равно ли е теглото на топка А на 3" - само относителни сравнения между теглата на някои топки, гледайки какво показва теглилката. В такъв случай дървото на решения е троично и трябва да има точно 24 листа => по формулата височината на дървото в най-добрия случай е roundup(log3(24)) = 3. Това означава, че всеки алгоритъм, който решава задачата, ще прави поне 3 сравнения в най-лошия случай.