Опитвам се да разбера времето за изпълнение на алгоритъм. Това е сортиране, което работи чрез разделяне на проблема на групи от 2/3 (това е CLR сортирането). Имам някои проблеми да го измисля, ето какво имам:
T(n)=3T([2n]/3)+1 (1 е, защото освен рекурсивните повиквания, има един обмен, който може или не може да бъде направен. Ако приемем, че е направен, това все още е само постоянна цена .)
T(n)=3T([2([2n]/3+1)]/3+1)+1
T(n)=3T([2([2([2n]/3+1)]/3+1)]/3+1)+1
T(n)=3T([2([2([2([2n]/3+1)]/3+1)]/3+1)]/3+1)+1
и т.н......докато можем да предположим, че в някакъв момент най-накрая сме достигнали основния случай за T(n) и ще получим постоянна стойност 1 за това време на изпълнение. Това ни дава:
3([2([2([2([2(...........)]/3+1)]/3+1)]/3+1)]/3+1)+1 with logn terms (that's the "......." in the middle). This gives:
3*(2n/3+1)^(logn)+1*logn
3*(2n/3+1)^(logn)+logn
Тогава мисля, че тъй като, ако основата на логаритъма беше 2n/3+1, можем да го опростим просто да бъде 3*logn+logn, можем да го направим. (Продължавам да чувам, че когато правим асимптотична нотация, основите на логаритмите, които сме избрали, нямат значение....)
Това става 4logn. Коефициентът намалява, за да стане просто logn.
Дали това е правилно? Не съм сигурен дали разширих това правилно или дали манипулациите ми с регистрационния файл бяха законни... Освен това какъв е този краен резултат - голямо-O, тита и т.н. Не съм сигурен какво гледам. ..
Благодаря.
