Algorytmy, silnia, przyjęte założenie

Cześć - zacząłem uczyć się algorytmów, potrzebuję pomocy osób które naprawdę rozumieją tą dziedzinę nauki.

Chodzi o pewne zagadnienie z książki którą czytam - przytoczę fragment.

"Rekurencyjna definicja silni
0! = 1
n! = n*(n-1)!, n >= 1, n należy do N

Odpowiadająca tej formule funkcja C++ ma następującą postać:

 
int silnia(int n)
{
if (n==0)
   return 1;
else
   return n*silnia(n-1);
}

Przyjmijmy dla uproszczenia założenie, bardzo zresztą charakterystyczne w tego typu zagadnieniach, że najbardziej czasochłonną operacją jest tutaj instrukcja porównania if. Przy takim założeniu czas, w jakim wykona się program możemy zapisać również w postaci rekurencyjnej:

  T(0) = tc
  T(n) = tc + T(n-1) --- dla n >= 1
 

T(0) -- czas wykonania funkcji dla danej wejściowej 0(zero)
tc -- czas wykonania jedenej instrukcji porównaia "

chodzi mi o zdanie ---> "Przyjmijmy dla uproszczenia założenie, bardzo zresztą charakterystyczne w tego typu zagadnieniach... "

Moje pytania brzmią -
Skąd wiedział jakie założenie trzeba przyjąć ??
Skąd wiedział że najbardziej czasochłonną operacją jest instrukcja porównania ??
Czemu akurat instrukcja porównania a nie np n*silnia(n-1) ????

Skąd wiedział że najbardziej czasochłonną operacją jest instrukcja porównania ??

Poczytaj o tym jak działa procesor i jak realizuje rozgałęzienia.

Skąd wiedział jakie założenie trzeba przyjąć ??

Wynikają z definicji silni nie wiem o co chodzi tutaj ?

Czemu akurat instrukcja porównania a nie np n*silnia(n-1) ????

Co autor tego pytania miał na myśli ?

0! = 1
n! = n*(n-1)!, n >= 1, n należy do N

T(n) = tc + T(n-1) <--- Rozumiem z definicji silni, ok ale czemu jest tu znak plus a nie znak mnożenia jak w definicji silni ?

No to chyba jednak nie rozumiesz ;]
Liczba operacji potrzebnych do wyliczenia silni z n to liczba operacji w tej funkcji (czyli jedno porównanie i jedno mnożenie) plus koszt policzenia silni z n-1. Przecież jak liczysz silnię z 3 to robisz
silnia(3) = porównanie + mnożenie + silnia(2) = porównanie + mnożenie + porównanie + mnożenie + silnia(1)
Skąd miałoby tam być mnożenie? Rząd zlożoności obliczeniowej służy do zliczania ile operacji wykonasz!

Problem z rozgałęzieniem jest taki że komputer zwykle stara się wcześniej wczytać i zdekodować operacje które będzie wykonywał. Tzn procesor jest podzielony na kawałki które mogą działać niezależnie. Kiedy jeden kawałek (ALU) wykonuje obliczenie, inny kawałek może w tym czasie dekodować kolejną operację którą procesor będzie wykonywał. Pozwala to przyspieszyć obliczenia.
Problem pojawia sie kiedy procesor nie wie jaki kod zaraz będzie miał wykonać. Masz ifa w kodzie więc procesor nie wie czy zaraz ma wykonać kod z bloku if czy z else. Procesor robi wtedy tzw branch-prediction ale to trochę loteria czy akurat trafi poprawnie.

Założenia nie muszą się zgadzać z rzeczywistością. Są jej modelem.

Vader_NoLord napisał(a):

Moje pytania brzmią -
Skąd wiedział jakie założenie trzeba przyjąć ??

Z doświadczenia. Znając pełne spektrum zachowań komputera można sobie jedno z nich wybrać jako modelowe. Nie sądzę żeby wymagał od Ciebie znajomości odpowiedzi na Twoje pytanie.

Vader_NoLord napisał(a):

Skąd wiedział że najbardziej czasochłonną operacją jest instrukcja porównania ??

Nie wiedział. Założył. Cyt. Przyjmijmy dla uproszczenia założenie,
W fizyce bywały zadania typu "przyjmijmy że jesteśmy mrówką wiszącą na stożku spadającym przy zerowym oporze powietrza"... - nie ma w tym wiedzy, jest abstrakcyjne założenie.

Vader_NoLord napisał(a):

Czemu akurat instrukcja porównania a nie np n*silnia(n-1) ????

Patrz wyżej. Równie dobrze mógł założyć że najbardziej kosztowne będzie wywołanie rekurencyjne lub mnożenie. Jak byłoby w rzeczywistości zależy od kompilatora.
Niektóre potrafią takie założenia obrócić w gruz.

W zadaniu chodzi o to żeby przy przyjętym modelu rzeczywistości móc obliczyć koszt całego wykonania obliczeń.

Shalom

Rząd zlożoności obliczeniowej służy do zliczania ile operacji wykonasz!

Nie wiem czy dobrze rozumiem
Czy dla pętli, najprostrzej pętli for mającej zinkrementować jakiś licznik
np
for(licznik = 0; licznik < 10; licznik++) {
//cos tam cos tam
}
można określić rząd złożnoności obliczeniowej czyli to ile operacji wykonuję ??
Jeśli tak czy to może wyglądać tak ?
Dla jednej inkrementacji:

Operacja 1
Przypisz 0 do licznik
Operacja 2
Porównaj czy licznik < 10
Operacja 3
Inkrementuj

Czyli wykonuję 3 operacje ??

Może tak być ???

Wykonujesz 3 operacje ale rząd złożoności będzie O(1) czyli stały. Bo nie zależy w żaden sposób od rozmiaru danych wejściowych. Co innego gdyby ta pętla miała n obiegów, wtedy masz 3*n operacji więc rząd O(n) czyli liniowy. Bo jeśli rozmiar danych na wejsciu wzrośnie 10 razy to algorytm będzie wykonywał się 10 razy dłużej. Gdybyś miał tam dwie zagnieżdżone pętle po n to miałbyś wtedy 3n operacji w każdym obiegu wewnętrznej pętli więc 2+3n w każdym obiegu zewnętrznej pętli. Czyli w sumie n*(2+3n) czyli O(n²), co zgadza się z intuicją. Bo jeśli n wzrośnie 10 razy to pętle wykonają sie w sumie 100 razy więcej więc czas działania algorytmu wzrośnie 100 razy.

Ok Shalom dzięki piękne za pomoc