개념지도 / 대학 맛보기 / 이산수학·컴퓨터

알고리즘과 계산 복잡도

algorithms and computational complexity 대학 앞으로

문제 푸는 단계별 절차. 입력이 커지면 단계가 얼마나 늘나(O 표기)

한 문장 직관 — 이것만 남으면 성공

알고리즘 복잡도는 "입력이 커질 때 시간이 얼마나 빨리 늘어나는가"다. O(n²)과 O(n log n)의 차이가 실무를 가른다.

결국 지수가 이긴다O(n²)과 O(n log n)의 차이가 실무를 가른다.

x 범위

처음엔 x²가 크지만 2^x가 반드시 추월한다.

컴퓨터과학의 핵심 질문. 왜 어떤 문제는 컴퓨터도 못 푸나

카드 정렬: 하나씩 끼우기 vs 반씩 나눠 합치기. 1000장이면 차이 100배

카드 10장을 두 방법으로 정렬하며 비교 횟수 세기

핵심 식

O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n)

✗ 컴퓨터가 빠르니 알고리즘은 상관없다.

왜 이렇게 생각하나
체감이 안 돼서.

어떻게 깨뜨리나
n=100만일 때 O(n²)은 10¹²번, O(n log n)은 약 2×10⁷번. 5만 배 차이. 하드웨어로 못 메운다.

P vs NP — 미해결 100만 달러 문제.