📌 시간 복잡도

알고리즘이란?

• 문제를 해결하기 위한 방법

예시

건너뛰기 혹은 살펴보기 전략

• 자취방 구하기
• 맛있는 음식점 찾아다니기
• 마음에 드는 옷 고르기

시간 복잡도

• 문제를 해결하는데 걸리는 시간과 입력의 함수 관계
• 계산법 = 핵심이 되는 연산이 무엇일까?
• 항상 최악의 경우를 시간복잡도로 쓴다.
• 최선의 경우는 어떤 알고리즘을 써도 만족스러운 경우가 나오기 때문에 최악의 경우를 시간복잡도로 사용

현실적 알고리즘

• Polynomial complexity (P 문제)
• sorting. dp

비현실적 알고리즘

• Nondeterministic Polynomial complexity (NP 문제)
• 소인수 분해 문제
  • ex) 21이 어떤 수들의 곱인지 구하는 것은 오래걸림
  • q와 p의 곱을 n이라하고 이를 공개키로 둔다.
• 해밀턴 경로 문제
• 컴퓨터로도 풀 수 없다
• 너무 오래 걸려

##

• 상태랑 행위를 검증할 때 ..
• 목키토를 안쓰고 서비스 안에서 다오를 쓰지만 서비스를 검증하고 싶다.
• 다오를 목으로 하냐 스텁으로 하냐
• 스텁은 then… 스텁은 값 검증을 안하면 됨
• 목은 값 검증을 해야함
• 목은 실제로 add가 동작했는지를 검증해야함