#1 Algorithms Efficiency

Algorithms

 - 어떤 문제를 해결하기 위한 일련의 절차, 방법

 - 어떤 일을 수행하기 위한 명령어들의 집합

 

 

 

특징

 - output을 생성한다.

 - 각 수행 단계가 명확하다.

 - 각 수행 단계는 실현이 가능해야 한다.

 - 유한한 단계를 수행하고 반드시 종료되어야 한다.

 

 

 

표현방법

 - 자연어 (natural language)

  : 일반적으로 우리가 사용하는 언어 (영어, 한글 등) 을 이용하여 알고리즘의 각 단계 설명

 - Flow chart

  : 알고리즘의 실행 순서를 diagram으로 나타낸 것

 - Pseudo code

  : 자연어와 가까운 기호로 코드를 흉내내어 알고리즘 구현

 - Programming language

  : 실제 프로그래밍 언어를 사용하여 표현

 

 

 

 

 

 

 

 

 

 

Algorithm Efficiency

 

좋은 프로그램이란?

 - 요구 조건을 정확하게 수행하는 프로그램

 - 메모리 사용을 최소화

 - 응답 시간, 처리 시간을 최소화

 - 가독성이 좋은 코드

 - 신뢰할 수 있는 코드

 - 코드에 쉽게 추가적인 확장이 가능한 코드

 - 유지보수가 용이한 코드

 

 

 

 

Algorithm efficiency 분석의 필요성

 -  Algorithm이  실제로 사용하기에 유용한지 여부 판단

 -  데이터 양이 많아질 경우 실행시간 예측 가능

 -  Algorithm 들을 비교하여 가장 나은 선택을 할 수 있게 함

 

 

 

Time complexity

 : 알고리즘의 실행 시간의 효율을 판단하는 기준

 

 

 

Big O notation

 : 주어진 데이터 규모를 함수 n으로 놓고 최고차항으로 비교하여 판단

O(1) < O(log n) < O(n) < O(n log n) < O($n^2$) < ... < O($2^n$)