알고리즘

문제를 해결하는 명령어들의 유합집합으로 다음의 사항을 만족해야함

• 입력 : 데이터가 0개 이상 존재한다.
• 출력 : 알고리즘 수행 후 적어도 한 가자의 결과가 생성된다.
• 명확성 : 각 명령어가 명확하고 모호하지 않다.
• 유한성 : 유한 단계 뒤에는 반드시 종료된다.
• 유효성 : 각 명령어가 기본적이어야한다.

성능 분석

프로그램에 대해 독립적인 시간, 공간을 분석하는 것

1. 공간 복잡도 : 프로그램을 실행시커 완료하는데 필요한 공간
2. 시간 복잡도 : 프로그램을 실행시켜 완료하는데 필요한 컴퓨터 시간의 양

시간 복잡도

실행 시간이 인스턴스 특성에 구문적으로 또는 의미적으로 독립성을 갖는 프로그램의 단위

• 각 시간복잡도 별 비교
  
• O(1) < O($logn$) < O(n) < O($nlogn$) < O($n^2$) < O($n^3$) < O($2^n$) < O(n!)
• O(1) : n에 관계없이 일정