Wpis z mikrobloga

via Wykop Mobilny (Android)
  • 0
@harnasiek: weź wypożycz jakąś książkę do algorytmiki. Szukaj pod złożoność obliczeniowa, jej wyliczanie.

Na studiach wymagają tego, a chyba nigdzie nie tłumaczą jak to liczyć.

@mk321:

nigdzie nie tłumaczą jak to liczyć

Bo nie ma jednej dobrej metody. Wyznaczanie złożoności może być dowolnie trudne. Może być dużo trudniejsze od wymyślenia samego algorytmu i udowodnienia jego poprawności. Są pewne standardowe sposoby, których czasem się używa ale na przykład wymagają więcej matematyki niż przeciętny student drugiego roku informatyki zna.
via Wykop Mobilny (Android)
  • 0
@ZdeformowanyKreciRyj: no ale wyliczenie podstawowych znanych algorytmów np. sortowania to chyba nie jest jakieś rocket science? Nie można by pokazać "gotowca" jak obliczyć? Lub jak nie ma jednego sposobu, to kilka różnych?

Na żadnej stronie, ani w żadnej książce tego nie widziałem.

Jedynie już gotowe wyliczone.
@harnasiek: w Cormenie masz całkiem ładnie rozpisane analizy algorytmów, niestety średnią złożoność ma tylko dobrze rozpisany quick sort, ale wątpię żebyś potrzebował czegoś trudniejszego
@Ralox: akurat potrzebuję trudniejszych, bo muszę rozpisać liczbe iteracji,porownan i zamian, zadanie totalnie z dupy bo na wykładach było jedynie wytłumaczone jak działają
@harnasiek: liczba iteracji to będzie złożoność, a liczba porownan i zamian zależy od algorytmu, w quick sorcie zamian powinno byc oczekiwanie dwa razy mniej niż porównań, w bubble sorcie podobnie, w insertion sorcie mniej więcej tyle samo, a w liniowe nie są oparte na porównaniach