Moderators: ArcherBarry , Fuzzwood
Berichten: 202
Het kan best zijn dat ik iets simpel over het hoofd zie in de volgende vraag.
De docent geeft de volgende afleiding. Waarbij
\(lg\)
de logaritme is met grondgetal 2.
\(3^{lg(n)} = 2^{lg(3)lg(n)} = n^{lg(3)}\)
Hierbij wordt
\(b^{log_b(y)} = y\)
twee keer toegepast.
Kan dit zomaar? Ik vind het namelijk onnatuurlijk, waarom is dit zo? Geldt in het algemeen dat
\(a^{log_c(n)} = n^{log_c(a)}\)
?
Berichten: 10.179
Waarom dat zo is, staat toch in de afleiding van je docent? Er zijn nog andere "afleidingen" mogelijk, maar je ziet toch dat het werkt?
Berichten: 202
Ok, dus dit klopt wel. Ik kon dit nergens op het internet vinden. Heeft dit ook nog een naam?
De vraag komt eigenlijk uit een vraag over hoe complex een algoritme is en met name of de complexiteit polynomiaal of exponentieel is. Hieruit blijkt dus dat het algoritme wel polynomiaal is lijkt me.
Kun je dan ook zeggen dat elke functie in de vorm
\( f(n) = a^{log_c(n)}\)
, polynomiaal is en niet exponentieel?
Pluimdrager
Berichten: 10.058
meijuh schreef: ↑ wo 31 okt 2012, 15:28
Kan dit zomaar? Ik vind het namelijk onnatuurlijk, waarom is dit zo? Geldt in het algemeen dat
\(a^{log_c(n)} = n^{log_c(a)}\)
?
Waarom probeer je dat niet met getallen uit ...
