Chapter1 - 알고리즘의 소개

단순 탐색

  • N개의 원소를 가진 리스트에서 N번 만에 답을 찾을 수 있다.

  • 선형시간(추측해야할 최대 횟수가 리스트의 길이와 같음) == O(n)

이진 탐색

  • N개의 원소를 가진 리스트에서 log2 N 번만에 답을 찾을 수 있다.

  • 리스트의 원소들이 정렬되어 있어야만 사용 가능하다.

  • 로그 시간 == O(log N)

빅오 표기법

  • 알고리즘의 최악의 경우 실행 시간을 표시

  • 알고리즘의 속도는 연산 횟수가 어떻게 증가하는지로 측정(시간으로 측정X)

외판원 문제

  • 실행 시간이 O(n!) 인 알고리즘

  • 다섯 개의 도시를 방문하는데 가장 짧은 경로를 택하는 문제, n개의 도시가 있다면 n!번의 연산이 필요. 현재 이 문제를 풀기 위한 더 빠른 알고리즘을 찾지 못함.

comments powered by Disqus