Задача

[Stefan Kanev]

Сега се сетих да питам вас.

Боря се със следната рекурентна зависимост:

T(n) = T(n-1) + T(n/2) + n

Каква е сложността? За горна граница намирам експоненциална, но ми се струва, че може и по-добре. За долна не съм сигурен.

Някой?

[Slavomir Kaslev]

Грубо, поне квадратична. Ако беше само B(n) = B(n-1) + n; B(0) = 1 щеше да е квадратично. Ще трябва да го помисля още ако искаш точна формула за T(n).

2013/12/24 Stefan Kanev <stefan...@gmail.com>

--
You received this message because you are subscribed to the Google Groups "Polyglot Quine" group.
To unsubscribe from this group and stop receiving emails from it, send an email to polyglot-quin...@googlegroups.com.
To post to this group, send email to polyglo...@googlegroups.com.
Visit this group at http://groups.google.com/group/polyglot-quine.
For more options, visit https://groups.google.com/groups/opt_out.

--
Slavomir Kaslev

[Dimitar Dimitrov]

Има ли някакъв общоприет assumption за дъно (сложността на T(0))?

Сравнително лесно можеш да разпишеш до T(n) = T(0) + n(n-1)/2 + ∑ T(i/2) (сумата на T(i/2) за i от 1 до n), т.е. би трябвало долната граница да е поне O(n²).

[Stefan Kanev]

2013/12/24 Dimitar Dimitrov <dmtrn...@gmail.com>

Има ли някакъв общоприет assumption за дъно (сложността на T(0))?

Сравнително лесно можеш да разпишеш до T(n) = T(0) + n(n-1)/2 + ∑ T(i/2) (сумата на T(i/2) за i от 1 до n), т.е. би трябвало долната граница да е поне O(n²).

За дъно можеш да приемеш T(1) = 1, ако има значение. Всъщност, може да применеш че T(n₀) = c₀, защото те интересува асимптотична сложност.

Че функцията е поне квадратична е ясно, понеже

T(n) = T(n-1) + n

е квадратична. Експериментирайки със стойности, обаче, стигам до подозрението, че е ω(n²) и ω(n³).

П.П.: Впрочем, не че съм експерт, ама доколкото разбирам тия неща, да кажеш "долната граница да е поне O(n²)" не е много смислено :) . Или поне при правилна употреба на нотацията.

[Stefan Kanev]

И да, искам възможно най-точния анализ. Поне квадратична и най-много експоненциална са най-точните неща, до които мога да достигна. Илюстрират се лесно със substitution method. Обаче повече детайли, аки някой може да ги измисли :)

2013/12/24 Stefan Kanev <stefan...@gmail.com>

[Slavomir Kaslev]

Под "поне квадратичен" имах пред вид, че алгоритъма не става. Като правило, квадратични алгоритми (и по-зле) не скалират/не са практични, за големи N. Иска ми се да кажа, че не се ползват, но няма да е вярно. В Chrome, например, ако намериш някъде квадратична операция е бъг.

2013/12/24 Stefan Kanev <stefan...@gmail.com>

--
You received this message because you are subscribed to the Google Groups "Polyglot Quine" group.
To unsubscribe from this group and stop receiving emails from it, send an email to polyglot-quin...@googlegroups.com.
To post to this group, send email to polyglo...@googlegroups.com.
Visit this group at http://groups.google.com/group/polyglot-quine.
For more options, visit https://groups.google.com/groups/opt_out.

--
Slavomir Kaslev

[Stefan Kanev]

2013/12/24 Slavomir Kaslev <slavomi...@gmail.com>

Под "поне квадратичен" имах пред вид, че алгоритъма не става. Като правило, квадратични алгоритми (и по-зле) не скалират/не са практични, за големи N. Иска ми се да кажа, че не се ползват, но няма да е вярно. В Chrome, например, ако намериш някъде квадратична операция е бъг.

Fair enough.

Интересува ме математиката, обаче, не практично приложение на алгоритъм с такова време (за какъвто не мога да се сетя).

[Dimitar Dimitrov]

Да, прощавай за лаишкото изказване, следващият път ще намеря символa за Омега голямо.

Интересното обаче е, че изглежда рекурентната зависимост характеризира линейна функция (kudos, wolframalpha).

Решена като функционално уравнение, споменатата зависимост води до T(n) = -2(n+1).

А нашия груб анализ, който assume-ва, че можем да правим съждения на базата на полуразвита форма, или пък да оценяваме, че допълнителен член в уравнението усложнява формата на функцията, е наистина доста неправилен, като се замисли човек.

--

[Slavomir Kaslev]

2013/12/24 Dimitar Dimitrov <dmtrn...@gmail.com>

Да, прощавай за лаишкото изказване, следващият път ще намеря символa за Омега голямо.

Интересното обаче е, че изглежда рекурентната зависимост характеризира линейна функция (kudos, wolframalpha).

Решена като функционално уравнение, споменатата зависимост води до T(n) = -2(n+1).

А нашия груб анализ, който assume-ва, че можем да правим съждения на базата на полуразвита форма, или пък да оценяваме, че допълнителен член в уравнението усложнява формата на функцията, е наистина доста неправилен, като се замисли човек.

Може. Обаче, аз мисля, че нашия груб анализ е верен, но не си въвел правилно граничните условия на рекурентаната зависимост за T(n) и затова wolframAlpha ти дава отрицателен резултат за положителни n. Ако му зададеш гранично условия, woflramAlpha се предава.  

--
Slavomir Kaslev

[Dimitar Dimitrov]

Попитах за гранични условия, точно защото са много определящи.

Забележи обаче, че оригиналният анализ, който направихме (все още твърдя, грешно), не разчиташе на използваните от теб гранични условия, просто беше неправилен assumption от наша страна, защото сме решили, че задачата е свързана с реален алгоритъм :)

Освен това, Стефан спомена, че се интересува от чисто математическата страна, доколкото разбрах, та конкретният пример ми се струва много готин.

Затова и въведох рекурентната зависимост без гранични условия.

--

[Delyan Kalchev]

Не върши ли работа някаква оценка от сорта (при достатъчно голямо положително n)

L(n) <= T(n) <= U(n)

където например
L(n) = L(n-1) + n
U(n) = 2U(n-1) + n

и L, U, T имат едни и същи начални условия.

2013/12/24 Stefan Kanev <stefan...@gmail.com>:

[Slavomir Kaslev]

2013/12/24 Dimitar Dimitrov <dmtrn...@gmail.com>

Попитах за гранични условия, точно защото са много определящи.

Забележи обаче, че оригиналният анализ, който направихме (все още твърдя, грешно), не разчиташе на използваните от теб гранични условия, просто беше неправилен assumption от наша страна, защото сме решили, че задачата е свързана с реален алгоритъм :)

Моя анализ беше *със* гранично условие:

> Ако беше само B(n) = B(n-1) + n; B(0) = 1 щеше да е квадратично.

Аssumptions, който използвах (и не написах) бе, че  T(n) >= 0, B(n) >= 0, T(n) - B(n) >= 0 for all n>0.

Което изглежда вярно, защото 

T(n) - B(n) = [ T(n-1) - B(n-1) ]  + T(n/2). 

Първия, член е положителен (по индукция по n), а втория от условието T(n) >= 0 for all n.

Може, разбира се, да не държиш, че T(n) е положително за положителни n. Но тогава не говорим за анализ на алгоритми. 

 

Освен това, Стефан спомена, че се интересува от чисто математическата страна, доколкото разбрах, та конкретният пример ми се струва много готин.

Затова и въведох рекурентната зависимост без гранични условия.

На 24 декември 2013 г., 23:37, Slavomir Kaslev <slavomi...@gmail.com> написа:

2013/12/24 Dimitar Dimitrov <dmtrn...@gmail.com>

Да, прощавай за лаишкото изказване, следващият път ще намеря символa за Омега голямо.

Интересното обаче е, че изглежда рекурентната зависимост характеризира линейна функция (kudos, wolframalpha).

Решена като функционално уравнение, споменатата зависимост води до T(n) = -2(n+1).

А нашия груб анализ, който assume-ва, че можем да правим съждения на базата на полуразвита форма, или пък да оценяваме, че допълнителен член в уравнението усложнява формата на функцията, е наистина доста неправилен, като се замисли човек.

Може. Обаче, аз мисля, че нашия груб анализ е верен, но не си въвел правилно граничните условия на рекурентаната зависимост за T(n) и затова wolframAlpha ти дава отрицателен резултат за положителни n. Ако му зададеш гранично условия, woflramAlpha се предава.  

--
Slavomir Kaslev

--

You received this message because you are subscribed to the Google Groups "Polyglot Quine" group.
To unsubscribe from this group and stop receiving emails from it, send an email to polyglot-quin...@googlegroups.com.
To post to this group, send email to polyglo...@googlegroups.com.
Visit this group at http://groups.google.com/group/polyglot-quine.
For more options, visit https://groups.google.com/groups/opt_out.

--
You received this message because you are subscribed to the Google Groups "Polyglot Quine" group.
To unsubscribe from this group and stop receiving emails from it, send an email to polyglot-quin...@googlegroups.com.
To post to this group, send email to polyglo...@googlegroups.com.
Visit this group at http://groups.google.com/group/polyglot-quine.
For more options, visit https://groups.google.com/groups/opt_out.

--
Slavomir Kaslev

[Delyan Kalchev]

Всъщност, ако

L(n) = 2L(n/2) + n

И така през пръсти това ми изглежда експоненциално.

Без никаква идея за контекст, моята интуиция е връзката между
рекурентните връзки и диференциалните уравнения. Гоrната формула за Т
прилича на ODE от първи ред с нелинейност в източника. Тези ODE задачи
лесно имат експоненциални решения, което пак е добре, защото спокойно
могат да станат и blow-up т.е. да стават безкрайни за крайно време
(крайно n).

2013/12/24 Delyan Kalchev <del...@gmail.com>:

[Iskren Chernev]

Пак стана flame war тука ... четете slashdot.com, ако толкова ви се
гледат пламъци
За задачата -- очевидно ограничение отгоре -- експоненциално. T(n) =
T(n-1) + T(n/2) + n < 2T(n-1) + n < n2^n
Отдолу (не че има смисъл): Т(n) = T(n-1) + T(n/2) + n >= 2T(n/2) + n =
O(nlogn) // добре познатите алгоритми за сортиране ала разделяй и
владей

Може да докажем, че е сложността е по-голяма от всеки полином n^k (за
фиксирано k). За целта е достатъчно да видим, че независимо от
константата c пред, от най-високите членове на T(n-1) и Т(n/2) излиза
cn^k - ckn^(k-1) ...(още членове от (n-1)^k)... + c(n^k)/2^k
Сега се вижда че това е повече от cn^k (по-точно (c + 1/2^k)n^k),
защото втория член от първата сума не може да погълне първия на
втората: i.e ckn^(k-1) ~> c(n^k)/2^k (~> значи асимпотично по-голямо).

Следователно не е полином (ако се чудите да слагате логаритми на
степен -- няма смисъл, просто качвате степента на полинома и вече
имате по-голяма асимпотика).
Значи е нещо по-голямо от полином и не по-голямо от експонента по n.
Освен да докажем, че е експонента ... :)

2013/12/24 Slavomir Kaslev <slavomi...@gmail.com>:

[Iskren Chernev]

Експонентата се доказва с индукция:

Допускаме, че T(n) <= 2^n, вярно за n <= n-1 (мързи ме да сменям букви)
T(n) = T(n-1) + T(n/2) + n <= 2^(n-1) + 2^(n/2) <*= 2^(n-1) + 2^(n-1) = 2^n

За звездичката: ще докажем, че 2^(n/2) ~> n. Това е същото като
2^(n/2) ~> n/2, което си е 2^n ~> n, което е ясно.
Туй е то. Ако някой знае функция между полином и 2^n да се обажда, аз не знам :)

2013/12/24 Iskren Chernev <iskren....@gmail.com>:

[Iskren Chernev]

Преди някой да ме поправи: между полином и 2^n има безкрайно много
сложности (именно v^n, където 1 < v < 2, и разни други поизводни на
тези, с полиноми/логаритми в числители и знаменатели). Остава да
докажем че не става с v < 2.

2013/12/24 Iskren Chernev <iskren....@gmail.com>:

[Iskren Chernev]

Ако трябва да съм честен тия работи не знам точно как се смятат. Но
мисля че доказах горна граница (1+eps) ^ n, а даже и (1+eps) ^
sqrt(n), за всяко положително eps (получава се обикновенно
неравенство, може да се предположи че n е "достатъчно голямо" -- т.е.
ако за достатъчно голямо е ОК е добре. Това е така, защото при
сложностни сметки може да се приемат всички стойности на функцията за
по-малки n -- константа ;-)). За други примери сметките стават сложни
и математиката ми е слаба.

Ако някой се "сети" коя функция е това, вероятно може да го докаже.
Обаче да се лутам с някакви криви експоненти и неравенства -- това не
е за всеки :) Вече се намираме в sub-exponential област, не знам как
да го рафинираме повече
(http://en.wikipedia.org/wiki/Time_complexity#First_definition).

2013/12/24 Iskren Chernev <iskren....@gmail.com>:

[Stefan Kanev]

И аз стигнах до същите изводи, които и Искрен, (без това за $(1 + \epsilon)^{\sqrt n}$), но наистина, искаше ми се да го хвана в Θ, което не знам дали е възможно.

2013/12/25 Iskren Chernev <iskren....@gmail.com>