4SUM има решение във време \Theta(n^2 x lg n): за всяка ненаредена двойка се записва сумата заедно със съответните индекси.  Тези наредени тройки се сортират по сумите.  За всяка сума с двоично търсене се открива, дали негацията и се среща или не.  Ако среща негацията, при това върху различни индекси, връщаме ДА.  Ако на нито една сума не открием негацията върху различни индекси, връщаме НЕ.  Важно е да се отчитат и индексите, а не само сумите.  Ако не отчитаме индексите, може погрешно да върнем ДА заради, примерно, наличието на три числа ... -10 ... -2 ... 6 ... в оригиналния масив:

  -10 + 6 = -4  ;    -2 + 6 = 4

Решенията на 4SUM в \Theta(n^3) време и \Theta(1) памет се признават.

Задачата с шахматната дъска и коня се решава тривиално в линейно време (линейно в големината на входа, тоест линейно спрямо N^2) чрез построяване на неориентиран граф, в който върховете са маркираните полета, а ребро м-у две полета се слага т.с.т.к. конят може да скочи от едното в другото директно.  Графът има ограничена от константа (а именно, 8) степен на върховете, следователно броят на ребрата е линеен в броя на върховете, и се строи във време \Theta(N^2). В този граф се пуска BFS от единият връх, съответстващ на ъгъл, и се гледа дали другият връх, съответстващ на ъгъл, е достижим.  Ако да, BFS ще даде и разстоянието м-у тях (в брой ходове на коня).

T(n) = \Theta(n^{\log_2{5}}) с МТ, случай 1

S(n) се намира с метода с характеристичното у-ние, само трябва да се съобрази, че от нехомогенната част "идват" две двойки и три на брой, корен-трети-от-две.  S(n) = \Theta(n x 2^n).

Последно модифициране: вторник, 3 юни 2014, 18:39