[Teoria złożoności] Wyznacz złożoność obliczeniową z iteracj

mkubasz
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 10 lis 2018, o 22:15
Płeć: Mężczyzna
Lokalizacja: Opole
Podziękował: 1 raz

[Teoria złożoności] Wyznacz złożoność obliczeniową z iteracj

Post autor: mkubasz »

Chciałbym wyznaczyć złożoność obliczeniową z dwóch iteracji. Jednak mam problem z rozbiciem sum.
Pierwsza iteracja:

Kod: Zaznacz cały

for(i=1;i<=n;i++) {
  for(j=1;j<=n;j++) {
    for(k=1;k<=i*j;k++){
       instrukcja;
    }
  }
}
Druga iteracja:

Kod: Zaznacz cały

for(i=1;i<=n;i++) {
  j=1;
  while(j<=2n) {
    for(k=i;k<=j;k++){
       instrukcja;
    }
   j+=2;
  }
}
Według mnie pierwsze równanie będzie wyglądało:
\(\displaystyle{ \sum_{i=1}^{n}\sum_{j=1}^{n} \sum_{k=1}^{i \cdot j}(1)}\)
Jednak nie mam pomysłu jak za tą ostatnią sumę się zabrać.
W drugiej części wydaje mi się, że będzie to:
\(\displaystyle{ \sum_{i=1}^{n}\sum_{j=1}^{n} \sum_{k=i}^{j}(1)}\)
Wydaje mi się, że może być w drugiej sumie n ponieważ iteracja zmienia się o dwa elementy.
Bardzo proszę o pomoc i skorygowanie równań. Szczególnie, że jeszcze nie do końca rozumiem jak to rozbijać i liczyć.
Ostatnio zmieniony 11 lis 2018, o 00:16 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

Re: [Teoria złożoności] Wyznacz złożoność obliczeniową z ite

Post autor: Afish »

W pierwszej:
\(\displaystyle{ \sum_{i=1}^{n}\sum_{j=1}^{n} \sum_{k=1}^{i \cdot j}(1)}\)
Dla \(\displaystyle{ i=1}\) mamy \(\displaystyle{ \sum_{j=1}^{n} \sum_{k=1}^{1 \cdot j}(1) = 1 + 2 + 3 + \ldots + n}\)
Dla \(\displaystyle{ i=2}\) mamy \(\displaystyle{ \sum_{j=1}^{n} \sum_{k=1}^{2 \cdot j}(1) = 2 + 4 + 6 + \ldots + 2n = 2\left(1 + 2 + \ldots + n\right)}\)
Dla \(\displaystyle{ i=3}\) będzie to \(\displaystyle{ 3\left(1 + 2 + \ldots + n\right)}\)
Teraz już będzie prosto, jak nie, to dalsza podpowiedź:
Ukryta treść:    
W drugiej chyba możesz zapisać tak: \(\displaystyle{ \sum_{i=1}^{n}\sum_{j=1}^{n} \sum_{k=i}^{2j-1}(1)}\)
mkubasz
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 10 lis 2018, o 22:15
Płeć: Mężczyzna
Lokalizacja: Opole
Podziękował: 1 raz

Re: [Teoria złożoności] Wyznacz złożoność obliczeniową z ite

Post autor: mkubasz »

Drugie udało mi się już rozwiązać. W ostatniej sumie mi się zdaje, że powinno być \(\displaystyle{ 2j}\) bo ostatnia iteracja jest mniejsze bądź równa się. Teraz jeszcze z pierwszym walczę.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

Re: [Teoria złożoności] Wyznacz złożoność obliczeniową z ite

Post autor: Afish »

Odpisałeś, gdy edytowałem post, zerknij ponownie.

Co do drugiego:
mkubasz pisze:W ostatniej sumie mi się zdaje, że powinno być \(\displaystyle{ 2j}\) bo ostatnia iteracja jest mniejsze bądź równa się.
Wtedy dla \(\displaystyle{ j=1}\) miałbyś \(\displaystyle{ \sum_{k=i}^{2}}\) więc o jeden obrót za dużo, ale mogę się mylić. Pytanie, czy interpretujesz ten symbol sumy jako \(\displaystyle{ 1+2}\) czy jako \(\displaystyle{ 1}\), dla mnie ta pierwsza interpretacja jest poprawna, ale mogę mieć inną definicję.
mkubasz
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 10 lis 2018, o 22:15
Płeć: Mężczyzna
Lokalizacja: Opole
Podziękował: 1 raz

Re: [Teoria złożoności] Wyznacz złożoność obliczeniową z ite

Post autor: mkubasz »

Dzięki wielkie! Masz rację!
ODPOWIEDZ