브라우저보다 빠른!
14 처지: 결정 문제, 복잡도 종류, 계산 복잡도 이론, 비결정론적 튜링 기계, 다항식, 튜링 기계, 점근 표기법, 상수 시간, 선형 시간, 알고리즘, 시간 복잡도, NP (복잡도), P (복잡도), P-NP 문제.
결정 문제
산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말..
새로운!!: 다항 시간와 결정 문제 · 더보기 »
복잡도 종류
복잡도 종류(複雜度 種類)는 계산 복잡도 이론에서 계산 복잡도에 따라서 문제를 분류한 것이.
새로운!!: 다항 시간와 복잡도 종류 · 더보기 »
계산 복잡도 이론
산 복잡도 이론(Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연. 이 때 알고리듬의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용.
새로운!!: 다항 시간와 계산 복잡도 이론 · 더보기 »
비결정론적 튜링 기계
비결정론적 튜링 기계(nondeterministic Turing machine, NTM)는 튜링 기계에서 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말. 이것은 비결정론적 유한 오토마타와 유사한 개념이.
새로운!!: 다항 시간와 비결정론적 튜링 기계 · 더보기 »
다항식
수학에서, 다항식(多項式)은 문자의 거듭제곱의 상수 배 여럿의 합을 표현하는 수식이.
새로운!!: 다항 시간와 다항식 · 더보기 »
튜링 기계
링 기계의 작동 방식을 묘사하는 그림 이론 전산학에서, 튜링 기계()는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이.
새로운!!: 다항 시간와 튜링 기계 · 더보기 »
점근 표기법
점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이.
새로운!!: 다항 시간와 점근 표기법 · 더보기 »
상수 시간
산 복잡도 이론에서 상수 시간(常數 時間) 또는 O(1)의 시간이란, 어떤 문제를 풀이하는데 필요한 수학적 연산 시간이 주어진 입력 자료에 관계 없이 일정할 때의 연산 시간을 의미.
새로운!!: 다항 시간와 상수 시간 · 더보기 »
선형 시간
선형 시간(線型時間, Linear time)이란, 계산 복잡도 이론에서, 입력의 길이 n에 대하여, 어떤 알고리즘의 실행시간이 선형(\colorBlueO(n))이 되는 것을 뜻. 예를 들면, 입력된 숫자열의 총합을 계산하는 순서는 숫자열의 길이에 비례하는 시간이 필요.
새로운!!: 다항 시간와 선형 시간 · 더보기 »
알고리즘
알고리즘(라틴어, 독일어: Algorithmus)은 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것을 말. 알고리즘은 연산, 데이터 진행 또는 자동화된 추론을 수행.
새로운!!: 다항 시간와 알고리즘 · 더보기 »
시간 복잡도
산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리.
새로운!!: 다항 시간와 시간 복잡도 · 더보기 »
NP (복잡도)
NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이.
새로운!!: 다항 시간와 NP (복잡도) · 더보기 »
P (복잡도)
P(PTIME 또는 DTIME(nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이.
새로운!!: 다항 시간와 P (복잡도) · 더보기 »
P-NP 문제
P는 NP에 속하지만, NP가 P에 속하는지 여부는 밝혀지지 않았다. P-NP 문제는 복잡도 종류 P와 NP가 같은지에 대한 컴퓨터 과학의 미해결 문제로 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻고 있. 1971년 스티븐 쿡이 그의 논문 〈The Complexity of Theorem Proving Procedures〉(정리 증명 절차의 복잡성)에서 처음으로 제안하였고 클레이 수학연구소에서 발표한 7개의 '밀레니엄 문제' 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있. 이것은 본래 1956년 쿠르트 괴델이 존 폰 노이만에게 썼던 편지에서 처음으로 언급되었.
새로운!!: 다항 시간와 P-NP 문제 · 더보기 »
