알고리즘 복잡도 성능 및 공간

Question

알고리즘 복잡성에 대한 수업을 연구 중이며 다른 복잡한 알고리즘이 있는지 알아야합니다. 내가 알고 공부 한 것은 2 가지 유형입니다. 1-는 BIG O 복잡성은 시간과 성능 및 기타입니다. 2는 메모리 복잡도 인 공간 복잡성이고, 알고리즘은 다른 종류의 복잡성을 가지고 있습니까? 알고리즘은 내가 놓친 다른 것에 의해 측정됩니까?

Answer 1

알고리즘의 점근 적 복잡성 - 예, 알고리즘 및 문제는 공간 및 시간으로 측정됩니다.

그러나 나는 그것에 대해 더 많이 말할 수 있습니다. 나는 몇 가지 문제를 해결하려고합니다 :

공간/시간 소비 분석하는 방법에서 유래 공간과 시간에 사용되는 알고리즘에 대한 분석의 4 개 일반적인 방법이있다
. big-O는 일련의 함수이지만 함수를 어떻게 파생 시켰는지 기억하십시오. 복잡성의 함수 (통상) 인 분석 방법은 다음 중 하나에 따라 유도되어

• 최상의 경우
• 보통 케이스
• 최악
• Amortized Analysis

이러한 각 방법은 모든 알고리즘에서 사용할 수 있으며 결과가 동일하지 않을 수도 있습니다. 예를 들어, 빠른 정렬은 최악의 경우 시간 복잡도가 O(n^2)이고 평균 사례 시간 복잡도가 O(nlogn)입니다.

더 많은 세트 : 큰 O 표기법에 추가
, 우리는 또한 복잡성을 표시하기 위해 다른 표기법을 사용합니다. 추가 일반적인 표기법 (사용의 공통성에 의해)은 다음과 같습니다

• 큰 세타 (Θ)
• 큰 오메가 (Ω)
• 작은
• 소형 오메가 (ω)

하지 오 Big Theta/Big O/notations ... 분석 방법과 혼동 될 수 있습니다 (최악의 경우/평균 경우/...)
Big Theta, Big O 및 Big O에 대한 자세한 내용 차이가 내기 그들 this thread

이론 복잡성에서 찾을 수 있습니다 싸우는 : 이론적 "Complexity Theory"의 분야에서
- 우리는 문제하지 알고리즘 분석 할 수 있습니다. 이 필드에서는 문제가 다항식으로 해결 될 수 있는지 (즉, 입력이 크기 n 인 경우 n의 일부 힘으로 문제를 해결할 수 있음) 다항식으로 검증됩니다 올바른지 확인하십시오). 그러나 다른 클래스도 있습니다.
일반적인 복잡성 클래스는 다음과 같습니다 또한

• NP
• P
• NP-Hard
• P Space

- 우리는 문제가 전혀 decidable/풀 수 있는지 관심이 있습니다. 문제의 해결의 가능성을 설명하는 일반적인 클래스는 다음과 같습니다

• R
• RE
• 코어

실제 세계 : 실제 응용 프로그램에서
- 우리가 약되므로주의 이론적 인 공간/시간 복잡성뿐만 아니라 상수 (ti의 절반을 차지하는 알고리즘 저와 같은 복잡성 등급에있을지라도, 다른 사람으로서의 저의 모습은 훨씬 낫습니다. 이는 복합 클래스가 상수를 무시하기 때문입니다.).
또한 프로그램/알고리즘의 구현 시간 및 유지 관리 가능성을 고려합니다.