szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 9 lis 2016, o 14:56 
Użytkownik

Posty: 9
Lokalizacja: Polska
Witam

Mam taki problem. Chciałbym wyznaczyć złożoność obliczeniową następującej pętli iteracyjnej:
Kod:
1
2
3
4
for(i=1;i<=n;i++)
   for(j=i;j<=n;j++)
      for(k=i+j;k<=i*i+j*j;k++)
         instrukcja;

O ile nie mam problemu jak to zrobić w przypadku gdy indeksy początkowe pętli wynoszą 1 (przydatne są wtedy wzory na sumy skończone), o tyle nie wiem od czego zacząć, gdy chcę policzyć/wyznaczyć stopień liczby n wynikające z tej sumy (reprezentacja powyższej pętli):

\sum_{i=1}^n\sum_{j=i}^n\sum_{k=i+j}^{i^{2}+j^{2}}1

Jak można zauważyć indeksy początkowe są zależne od siebie. Może coś ja źle robię szukając sposobu by móc zastosować wspomniane już wzory na sumy skończone.

Jakaś rada? Sugestia od czego zacząć?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 9 lis 2016, o 18:17 
Moderator
Avatar użytkownika

Posty: 7705
Lokalizacja: Wrocław
Jeśli wystarczy Ci asymptotyczne tempo wzrostu, to można zrobić tak:

$ \begin{align*}
\# \{ \text{przebieg pętli} \} & = \# \{ (i, j, k) \in \NN^3 : 1 \le i \le j \le n \hspace{6pt} \& \hspace{6pt} i+j \le k \le i^2+j^2 \} \\[1ex]
& \ge \# \left\{ (i, j, k ) \in \NN^3 : 1 \le i \le \frac{n}{3} \hspace{6pt} \& \hspace{6pt} \frac{n}{3} \le j \le \frac{2n}{3} \hspace{6pt} \& \hspace{6pt} \frac{n}{3} + \frac{2n}{3} \le k \le \left( \frac{n}{3} \right)^2 \right\} \\[1ex]
& \sim \frac{n}{3} \cdot \frac{n}{3} \cdot \left( \frac{n^2}{9} - n \right) \sim c \cdot n^4
\end{align*} $
Góra
Mężczyzna Offline
PostNapisane: 9 lis 2016, o 21:03 
Użytkownik

Posty: 9
Lokalizacja: Polska
Z tego to dopiero nic nie rozumiem :P

Z tymi sumami nie da się nic zrobić? Jakoś uprościć by można było skorzystać z prostych wzorów na sumy skończone?
Góra
Mężczyzna Offline
PostNapisane: 9 lis 2016, o 21:35 
Użytkownik

Posty: 1073
Lokalizacja: Lublin/Warszawa
Oczywiście, że się da.
Trzeba będzie wielokrotnie korzystać ze wzorów na sumy:
https://pl.wikisource.org/wiki/Sumy

Będę korzystał z takiej własności, że licząc sumę od pewnego indeksu j do n, ja tak na prawdę liczę ją od 1 do n, a potem odejmuję to co jest niepotrzebne, czyli sumę od 1 do j - 1.
\sum_{i=1}^n\sum_{j=i}^n\sum_{k=i+j}^{i^{2}+j^{2}}1 = \sum_{i=1}^n\sum_{j=i}^n\left(  i^{2}+ j^{2}-\left(i+j - 1 \right)   \right) = \sum_{i=1}^n\sum_{j=i}^n i^{2} + \sum_{i=1}^n\sum_{j=i}^n j^{2} - \sum_{i=1}^n\sum_{j=i}^n i - \sum_{i=1}^n\sum_{j=i}^n j + \sum_{i=1}^n\sum_{j=i}^n 1=\sum_{i=1}^n i^{2}\left( n-\left( i - 1\right) \right)  + \sum_{i=1}^n\left(  \frac{n\left( n+1\right)\left( 2n+1\right)  }{6} -  \frac{\left( i - 1\right) i\left( 2i - 1\right) }{6} \right) -\sum_{i=1}^n i\left( n - \left( i - 1\right) \right) -  \sum_{i=1}^n\left(  \frac{n\left( n+1\right)  }{2} -  \frac{\left( i - 1\right) i}2}\right)+ \frac{n\left( n+1\right) }{2} =...

No i dalej trzeba rozbić wyrażenia pod sumami na składniki, czyli zrobić więcej sum i podoliczać. Widać, że to jest O\left(  n^{4} \right).
Góra
Mężczyzna Offline
PostNapisane: 9 lis 2016, o 23:25 
Użytkownik

Posty: 9
Lokalizacja: Polska
Mruczek, Dziękuję za odpowiedz. Co nieco mi się już rozjaśniło. Mam jeszcze jedno pytanie... Na czym oparłeś swoje szacowanie co do wyniku (że wyjdzie n^4)? Może to kwestia doświadczenia z tego typu problemami, ale jak taki niuans wychwyciłeś?

@edit
Rozwiązałem zadanko i wyszło jak mówiliście O(n^4).
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Oblicz, ile podzielników, będących liczbami naturalnymi,  chef  1
 oblicz prawdopodobieństwo zdarzeń - zadanie 2  Mechu  0
 Oblicz - zadanie 4  caroline  2
 Oblicz z silnia  nice88  0
 Silnia-oblicz wartość wyrażenia  deftfan  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl