Różnica między złożonością czasową a złożonością obliczeniową

Czy w przypadku pomiaru złożoności algorytmu jest to złożoność czasowa czy złożoność obliczeniowa? Jaka jest różnica między nimi?

Kiedyś obliczałem maksymalną (najgorszą) liczbę podstawowych (najbardziej kosztownych) operacji w algorytmie.

complexity-theory terminology algorithm-analysis time-complexity Mediana Hilal
źródło

Nie jest to odpowiedź na twoje pytanie, ale biorąc pod uwagę twoje zainteresowanie takimi

„złożoność algorytmu” w odniesieniu do asymptotycznego działania jest (często używanym) błędem. Chcesz powiedzieć „asymptotyczne środowisko uruchomieniowe”.

Raphael

Odpowiedzi:

Złożoność obliczeniowa jest po prostu bardziej ogólnym terminem, ponieważ czas nie jest jedynym zasobem, jaki chcielibyśmy rozważyć. Następną najbardziej oczywistą jest przestrzeń, z której korzysta algorytm, a zatem możemy mówić o złożoności przestrzeni , również jako części złożoności obliczeniowej. Rzeczywiście, możemy to zrobić w przypadku każdego stosowanego przez Ciebie środka, oczywiście niektóre środki są bardziej przydatne niż inne.

Tak więc zliczenie liczby kroków, które algorytm wykonuje w najgorszym przypadku, określa złożoność czasową związaną z rozwiązywanym przez niego problemem, zliczanie ilości pamięci / liczby wykorzystywanych komórek, co wiąże się ze złożonością przestrzeni itp.

Pamiętaj także, że jeśli chcesz być ścisły, złożoność odnosi się do problemu, a nie algorytmu, więc problem ma ograniczenia złożoności, algorytm ma ograniczenia zasobów (czas działania, wykorzystanie miejsca ...). To tylko kwestia formalnej definicji, teoria złożoności dotyczy problemów. Tak, algorytmy są kluczowym narzędziem dla problemów analizy i złożoności i algorytmika są ściśle ze sobą powiązane, ale formalnie nie powiedziałbym Merge-Sort (algorytm) jest , to problem , który jest w . Scalanie-sortowanie wykorzystuje określone zasoby ( $P$ $\mathsf{Sorting}$ $P$ $O(n\log n)$ kroki na przykład). Ograniczenie zasobów i poprawność algorytmu implikują złożoność (górną granicę) problemu, ale są to różne rzeczy. także -Complete pod -reductions, złożoność związaną może być tylko bardzo podane dla problem (ale ma wpływ algorytmiczne). $\mathsf{Sorting}$ $TC^{0}$ $AC^{0}$

Luke Mathieson
źródło

@ shekharsuman Przez problem rozumiem formalne pojęcie problemu obliczeniowego (np. k-Vertex Cover), a nie ogólne znaczenie. Złożoność obliczeniowa to klasyfikacja problemów obliczeniowych, więc w sensie formalnym złożoność odnosi się do tego, co możemy powiedzieć o problemie. Wyniki dotyczące algorytmów mówią nam o złożoności problemów, ale same w sobie nie są wynikami złożoności (ale nieformalnie mówimy o złożoności algorytmu).

Luke Mathieson

@ shekharsuman akapit otwierający strony wikipedii jest całkiem dobrym podsumowaniem.

Luke Mathieson

@Luke Dzięki, dzięki temu wszystko jest jasne. Jeśli jednak mogę użyć idiomu „najczęściej używanego rodzaju złożoności do formalnej oceny algorytmów” (chociaż wiem, że nie jest to precyzyjne). Jaki byłby czas vs. obliczeniowy? Myślę, że ogólnie rzecz biorąc, najważniejszą rzeczą jest czas, ponieważ zasoby są w pewnym sensie rozszerzalne!

Mediana Hilal

@MedianHilal jest rzeczywiście najczęściej uważanym miernikiem złożoności problemu. Przestrzeń kosmiczna nie jest zbyt daleko w tyle (przynajmniej przez teoretyków złożoności i ludzi zajmujących się bardzo dużymi zbiorami danych, rzadziej z dnia na dzień).

Luke Mathieson

-2

Cyklomatyczną złożoność często stosuje się jako miarę złożoności obliczeniowej, przydatny przykład podano w /programming/9097987/calculation-of-cyclomatic-complexity

Może istnieć wiele różnych (prawdopodobnie zagnieżdżonych) ścieżek w algorytmie, co daje mu wysoką złożoność cykliczną, ale nie ma pętli, które zapewniają złożoność w niskim czasie. Program z pojedynczą pętlą miałby niską złożoność cykliczną, ale być może wysoką złożoność czasową.

Cyklomatyczna złożoność jest często używana jako miara konserwacji wymaganej dla kodu. Bardziej szczegółową dyskusję można znaleźć w http://docs.sonarqube.org/display/SONAR/Bad+Distribution+of+Complexity . Różni się to od złożoności czasowej, którą jest pomiar czasu wykonywania kodu i może być wykorzystywany do oceny postrzegania przez użytkowników skuteczności systemu.

velvetytoast
źródło

Pytanie dotyczy złożoności obliczeniowej, a nie złożoności cyklicznej!

Am_I_Helpful

Możesz przeczytać OP - pyta o złożoność algorytmu - Złożoność cykliczna daje statyczną miarę złożoności obliczeniowej algorytmów - spróbuj dodać pozytywne informacje zwrotne następnym razem

velvetytoast

Cyklomatyczna złożoność nie mierzy złożoności obliczeniowej. Złożoność obliczeniowa odnosi się do czasu działania, a nie do stopnia złożoności struktury kodu źródłowego.

@DW Dokładniej, złożoność obliczeniowa odnosi się do zasobów wymaganych do rozwiązania problemu (które mogą obejmować spacje, naprzemienność, wywołania wyroczni itp., A także czas).

David Richerby

@DavidRicherby Nie jestem ekspertem w tej kwestii, więc proszę poprawić, jeśli jest źle. Statyczne miary złożoności, takie jak rozmiar programu, odgrywają pewną rolę w niektórych sytuacjach. Czy mam rację, że jest to bardziej związane ze złożonością Kołmogorowa. Czy dotyczyłoby to również złożoności cyklomatycznej? Jeden rodzaj złożoności pisania programów lub problemów, a drugi ich rozwiązywania lub uruchamiania ... być może krótkie przybliżenie sytuacji. Nie jestem pewien, czy napisałbym rozsądne pytanie w tej sprawie.

babou