Wpis z mikrobloga

@Nefaru: Już się gubię..
Algorytm polega na wykonaniu n^3 operacji mnożenia, ale całość działa równolegle na p procesorach, więc każdy procesor wykona (n^3)/p operacji mnożenia.

Mam podać złożoność przetwarzania - to jaka ona w końcu jest? :D
@AHScorpii: No widzisz, sam stwierdzasz, że algorytm wykonuje n^2 operacji mnożenia, więc złożoność algorytmu to n^2.
Teraz kwestia procesorów: nie każdy procesor wykona (n^2)/p operacji mnożenia, ale średnio wykona (n^2)/p operacji, bo to będzie zależne od rodzaju danych. I teraz taka kwestia, jeżeli uznajesz, że liczba procesorów jest częścią algorytmu i ją podajesz jakby do samego algorytmu - ok, uznaj ją za zmienną, kombinuj ze złożonością na dwóch zmiennych. Jeżeli liczba
@AHScorpii: zależy jak bardzo możesz zrównoleglić obliczenia i czy p jest czymś ograniczone. (W całym komentarzu zakładam p nieograniczone)
Czysto teoretycznie, nawet jeśli mamy nieskończenie wiele procesorów, to niektóre algorytmy mogą nie dać przyśpieszenia w ogóle. Wszystko zależy od długości ścieżki krytycznej pracy która jest do wykonania. Na przykład mnożenie macierzy w takim modelu zrównolegla się całkiem dobrze (każda komórka macierzy wynikowej nirzależnie liczona przez inny proces). Natomiast nie wiem w
@Saly: No dobrze, ale jak już wybierzesz model obliczeń, to nie będzie miało znaczenia, ile masz rdzeniów, prawda? O to mi w zasadzie chodziło, że jak już zdecydujesz, co to jest złożoność obliczeniowa, jakie operacje są elementarne etc., to nie będzie miało znaczenia, gdzie ten algorytm jest wykonywany.