[Programmiren]

#pytanie #programowanie #naukaprogramowania
Czołem mirki. Zastanawiam się nad analizą czasową algorytmu. Jeżeli jest 1..sqrt(n) w pętli zewnętrznej to wychodzi, że jest O(sqrt(n)), dalej idąc mam przypisanie czyli O(n) i potem pętla while dokonująca dodawania czyli O(n). Czy wychodzi na to, że czas potrzebny to: O(sqrt(n)*n^2 )? Jeżeli się mylę pomoglibyście mi to zrozumieć? Od czego zależy złożoność logn i nlogn?
http://pastebin.com/kMXWaCfe

[fake_name]

@Programmiren: Przypisanie nie ma złooności O(n). Przeczytaj sobie mój wpis tam starałem się to juz wyjaśnić

[Programmiren]

@fake_name: Czyli w takim razie będzie to sqrt(n)*n? Wiem w sumie, że sqrt(n) jest poprawne, czy masz pomysł co do reszty?

[fake_name]

@Programmiren: btw. tam jakiegos return nie brakuje? Dla uproszczenie (cała ta notacja to uproszczenie) uznajmy że dodawanie i przypisanie zajmuje czas T. Wobec tego mamy pętla1:T*sqrt(n) pętla 2: T*sqrt(n), czyli 2 pętle po sqrt(n), a sqrt(n)*sqrt(n) = n (wiem że to matematycznie nie jest dokońca poprawnie, ale jest juz pozno :P). Więc złozoność olbiczeniowa to O(n) - czyli rosnie liniowo wraz z instancja problemu. O ile wiem są jakies algorytmy

[Programmiren]

@fake_name: Pytałem się znajomego kilka minut temu i napisał, że jest to log(sqrt(n))*sqrt(n) tylko nie miał czasu mi odpowiedzieć dlaczego tak, masz może pomysł?

[fake_name]

@Programmiren: YYY nie wiem skąd ma ten log :P

[Programmiren]

@fake_name: ale tam jest ( log sqrt(n) ) * sqrt(n) ( ͡° ͜ʖ ͡°)