• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Złożoność algorytmów

Object Storage Arubacloud
0 głosów
237 wizyt
pytanie zadane 14 kwietnia 2019 w C i C++ przez LukiLL Początkujący (270 p.)

Cześć, mam problem z podaniem funkcji złożoności obliczeniowej do następującego programu :

for(int i=1; i<=n; i++){
 int j=n;
 while(j>=1){
 j= j/2;
 }
}

Mniej więcej wiem jak to robić tylko mam problem z funkcją wew.

Jeśli byłby ktoś wstanie dać jakąś wskazówkę i to wytłumaczyć byłbym wdzięczny :) 

2 odpowiedzi

+1 głos
odpowiedź 14 kwietnia 2019 przez mrspock1 Mądrala (6,420 p.)
Pętla wewnętrzna wygląda na logarytm przy podstawie 2 z n, czyli razem rząd jest n*log(n)
0 głosów
odpowiedź 14 kwietnia 2019 przez radek024 Szeryf (77,160 p.)
Śmiesznie, bo jutro mam to do zaliczenia. Najlepiej - imo - podstawiać wartości, pomiędzy czwartą a piątą linią dać coś co zlicza kroki algorytmu. Idąc tym tokiem dostaniemy kolejne wartości, które będą się układać w pewną całość. Łatwo zauważyć, że ilość operacji zwiększa się przy wielokrotnościach dwójki. Może być to zatem funkcja wykładnicza. Ale czy na pewno? Dla n=16 mamy 5 operacji, więc raczej to funkcja odwrotna, czyli logarytm. O jakiej podstawie? Jak wiemy a^x=b wtedy i tylko wtedy gdy log o podstawie a z b=x. Czyli podstawa=2.

Sposób jest toporny, ale nie wiem jak to inaczej ugryźć.

Podobne pytania

0 głosów
1 odpowiedź 329 wizyt
pytanie zadane 14 czerwca 2021 w Algorytmy przez Tanormalnie Użytkownik (550 p.)
0 głosów
0 odpowiedzi 322 wizyt
0 głosów
1 odpowiedź 1,001 wizyt
pytanie zadane 6 grudnia 2017 w C i C++ przez blacktiger23 Nowicjusz (160 p.)

92,677 zapytań

141,581 odpowiedzi

320,061 komentarzy

62,039 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...