Често се среща такова "решение" на зад 5:

  Масивът се състои от q на брой подмасива, всеки с дължина p. Знаем от лекции, че сортирането на всяко от парчетата има долна граница p lg(p).  Парчетата са q общо, оттук долна граница pq lg(p) = n lg(p).


Това не е решение.  Ако беше аргумент за горна граница, щеше да е ОК: наистина, ако сортираме всяко от парчетата, ще имаме сортиран масив, защото всяко парче е по-малко, поелементно, от всяко следващо.

Но ние искаме аргумент за ДОЛНА граница.  Това, че задачата МОЖЕ да се реши с q на брой независими сортирания не влече автоматично, че ТРЯБВА да се извършат q на брой независими сортирания.  То е *вярно*, но трябва да се *докаже*!  Не е очевидно от общи съображения.  Ако ще се прави доказателство по този начин, трябва да се докаже, че сортирането на всяко парче става независимо от останалите, така че на практика правим q отделни сортировки, щем-не щем;  да се каже, че сравнения на елементи от различни парчета са безсмислени, защото резултатът е предварително известен.  По същество, това би било доказателство с редукция, която трябва да се формулира внимателно.

Много по-лесно е да се ползва директен аргумент с дърво на сравненията: да се сметне броят на съществено различните входове (p!)^q, да се каже, че листата са поне толкова, и да се каже, че височината е поне lg( (p!)^q ), което е, асимптотично, n lg p.

Последно модифициране: неделя, 19 май 2019, 18:56