#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: 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ł?
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