계산 복잡도

컴퓨터 과학의 핵심 개념

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

복잡도 클래스

복잡도 클래스

  • 다항시간 (P)
  • 비결정적 다항시간 (NP)
  • NP-Complete
  • NP-Hard

전체 문제 복잡도 공간을 보여주는 애니메이션

컴퓨터 과학의 핵심 개념

P (다항시간)

문제 공간 P를 보여주는 이미지

Complexity Class --> P (Polynomial Time)
What it means 빠르고 효율적으로 해결 가능
Example 리스트 정렬
Analogy "문서를 가나다순으로 정리"
Key Point 계산적으로 "쉬운" 문제
1 https://www.baeldung.com/cs/p-np-np-complete-np-hard
컴퓨터 과학의 핵심 개념

NP (비결정적 다항시간)

문제 공간 P와 NP를 보여주는 이미지

Complexity Class --> NP (Non-deterministic Polynomial Time)
What it means 해의 검증은 쉬우나 새 해를 찾기는 어려움
Example 스도쿠 해답의 정당성 검증
Analogy "정보가 누락된 문서 찾기"
Key Point 검증은 "쉬움", 새로운 해 찾기는 어려움
1 https://www.baeldung.com/cs/p-np-np-complete-np-hard
컴퓨터 과학의 핵심 개념

NP-Complete

문제 공간 P, NP, NP-Complete를 보여주는 이미지

Complexity Class --> NP-Complete
What it means NP 중 가장 어려움. 모든 NP를 대표
Example 외판원 순회 문제
Analogy "복잡한 퍼즐: 확인은 쉬우나 풀기는 어려움"
Key Point 효율적 해법 미발견. 하나 찾으면 모든 NP 해결
1 https://www.baeldung.com/cs/p-np-np-complete-np-hard
컴퓨터 과학의 핵심 개념

NP-Hard

문제 공간 P, NP, NP-Complete, NP-Hard를 보여주는 이미지

Complexity Class --> NP-Hard
What it means NP-Complete만큼 어렵거나 더 어려움
Example 복잡한 의존성을 가진 최적 스케줄링, 검증 불가
Analogy "제약이 많은 최적 회의 시간 잡기, 빠른 검증 불가"
Key Point 실용적으로 풀기 불가능할 수 있음
1 https://www.baeldung.com/cs/p-np-np-complete-np-hard
컴퓨터 과학의 핵심 개념

P=NP의 큰 미스터리

오랜 연구 질문인 P=NP인가를 묻는 도식

컴퓨터 과학의 핵심 개념

연습해 봅시다!

컴퓨터 과학의 핵심 개념

Preparing Video For Download...