심벌 마크
유니온백과
통신
다운로드하기 Google Play
새로운! 안드로이드 ™에 유니온백과를 다운로드 할 수 있습니다
비어 있는
브라우저보다 빠른!
 

계산 복잡도 이론

색인 계산 복잡도 이론

산 복잡도 이론(Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연. 이 때 알고리듬의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용.

21 처지: EXPSPACE, EXPTIME, 결정 문제, 복잡도 종류, 계산 이론, 비결정론적 튜링 기계, 다항식, 튜링 기계, 점근 표기법, 추상 기계, 컴퓨터 과학, 최적화, 함수, 알고리즘, , 시간 복잡도, L (복잡도), NL (복잡도), NP (복잡도), P (복잡도), PSPACE.

EXPSPACE

산 복잡도 이론에서 EXPSPACE는 결정론적 튜링 기계가 \colorBlueO(2^p(n)) 공간을 써서 풀 수 있는 판정 문제의 집합이.

새로운!!: 계산 복잡도 이론와 EXPSPACE · 더보기 »

EXPTIME

산 복잡도 이론에서 복잡도 종류 EXPTIME(EXP라고도 한다)은 결정론적 튜링 기계가 \colorBlueO(2^p(n))시간에 풀 수 있는 모든 판정 문제의 집합이.

새로운!!: 계산 복잡도 이론와 EXPTIME · 더보기 »

결정 문제

산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말..

새로운!!: 계산 복잡도 이론와 결정 문제 · 더보기 »

복잡도 종류

복잡도 종류(複雜度 種類)는 계산 복잡도 이론에서 계산 복잡도에 따라서 문제를 분류한 것이.

새로운!!: 계산 복잡도 이론와 복잡도 종류 · 더보기 »

계산 이론

산 이론(計算理論, Theory of computation)은 컴퓨터 과학의 한 갈래로, 어떤 문제를 컴퓨터로 풀 수 있는지, 또 얼마나 효율적으로 풀 수 있는지를.

새로운!!: 계산 복잡도 이론와 계산 이론 · 더보기 »

비결정론적 튜링 기계

비결정론적 튜링 기계(nondeterministic Turing machine, NTM)는 튜링 기계에서 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말. 이것은 비결정론적 유한 오토마타와 유사한 개념이.

새로운!!: 계산 복잡도 이론와 비결정론적 튜링 기계 · 더보기 »

다항식

수학에서, 다항식(多項式)은 문자의 거듭제곱의 상수 배 여럿의 합을 표현하는 수식이.

새로운!!: 계산 복잡도 이론와 다항식 · 더보기 »

튜링 기계

링 기계의 작동 방식을 묘사하는 그림 이론 전산학에서, 튜링 기계()는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이.

새로운!!: 계산 복잡도 이론와 튜링 기계 · 더보기 »

점근 표기법

점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이.

새로운!!: 계산 복잡도 이론와 점근 표기법 · 더보기 »

추상 기계

상기계(抽象機械, abstract machine)는 컴퓨터 하드웨어나 소프트웨어의 이상적인 모형이.

새로운!!: 계산 복잡도 이론와 추상 기계 · 더보기 »

컴퓨터 과학

학()은 전산 이론, 하드웨어 및 소프트웨어에 중점을 둔 정보과학의 한 분야이.

새로운!!: 계산 복잡도 이론와 컴퓨터 과학 · 더보기 »

최적화

적화(最適化)는 다음을 가리키는 말이다.

새로운!!: 계산 복잡도 이론와 최적화 · 더보기 »

함수

수를 상자에 비유한 그림. 수학에서, 함수(函數) 또는 사상(寫像)은 첫 번째 집합의 임의의 한 원소를 두 번째 집합의 오직 한 원소에 대응시키는 대응 관계이.

새로운!!: 계산 복잡도 이론와 함수 · 더보기 »

알고리즘

알고리즘(라틴어, 독일어: Algorithmus)은 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것을 말. 알고리즘은 연산, 데이터 진행 또는 자동화된 추론을 수행.

새로운!!: 계산 복잡도 이론와 알고리즘 · 더보기 »

셈()은 물체의 개수를 헤아리는 행동이.

새로운!!: 계산 복잡도 이론와 셈 · 더보기 »

시간 복잡도

산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리.

새로운!!: 계산 복잡도 이론와 시간 복잡도 · 더보기 »

L (복잡도)

산 복잡도 이론에서 L(LSPACE 또는 DLOGSPACE)은 결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이.

새로운!!: 계산 복잡도 이론와 L (복잡도) · 더보기 »

NL (복잡도)

산 복잡도 이론에서 NL(Nondeterministic Logarithmic-space)은 비결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이.

새로운!!: 계산 복잡도 이론와 NL (복잡도) · 더보기 »

NP (복잡도)

NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이.

새로운!!: 계산 복잡도 이론와 NP (복잡도) · 더보기 »

P (복잡도)

P(PTIME 또는 DTIME(nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이.

새로운!!: 계산 복잡도 이론와 P (복잡도) · 더보기 »

PSPACE

산 복잡도 이론에서 PSPACE는 결정론적 튜링 기계나 비결정론적 튜링 기계가 시간은 얼마든지 쓸 수 있고, 공간은 다항 공간만 써서 풀 수 있는 판정 문제들의 집합이.

새로운!!: 계산 복잡도 이론와 PSPACE · 더보기 »

여기로 리디렉션합니다

계산복잡도이론, 복잡도 이론.

나가는들어오는
이봐 요! 우리는 지금 Facebook에 있습니다! »