알고리즘?

컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법
어떠한 문제를 해결하기 위한 절차 (예 : 1부터 100까지의 합)

알고리즘을 표현하는 방법

• 슈도코드
  말 그대로 흉내만 내는 코드
  특정 프로그래밍 언어가 아닌 일반적인 언어로 문법을 흉내내어 알고리즘을 써놓은 코드
  실제 프로그래밍 언어로 작성된게 아니라 컴퓨터로 실행할 수 없음
  알고리즘의 모델을 대략적으로 모델링하는데 쓰임

• 순서도
  프로그램 작업이나 흐름도를 순서에 따라 여러가지 기호와 문자로 나타낸 도표
  흐름도, 프로그램의 논리적 흐름, 데이터 처리 과정을 표현
  프로그램 작성 전 프로그램의 전체적 흐름과 과정 파악을 위해 필수적으로 거쳐야 되는 작업

무엇이 좋은 알고리즘인가?

1. 정확성 - 얼마나 정확하게 동작하는가?
2. 작업량 - 얼마나 적은 연산으로 원하는 결과를 얻어내는가?
3. 메모리 사용량 - 얼마나 적은 메모리를 사용하는가?
4. 단순성 - 얼마나 단순한가?
5. 최적성 - 더 이상 개선할 여지 없이 최적화 되었는가?

어떤 알고리즘을 사용하느냐에 따라 문제해결에 차이가 나타남
많은 문제에서 성능 분석의 기준으로 알고리즘 작업량 비교

1+2+3+...+100 => 99번의 연산(덧셈)
100*(1+100)/2 => 3번의 연산(덧셈 1, 곱셈1, 나눗셈 1)
100이 아니라 1000이면, 10000이면 둘의 연산수의 차이는 기하급수적으로 늘어남

시간복잡도

실제 걸리는 시간 측정
실행되는 명령문의 개수를 계산

시간 복잡도를 표현하는 방법 중 1 = 빅-오 표기법

O(3n+2) = O(n)

일반적으로 로그함수가 일차함수보다 빠르고, 일차함수는 이차함수보다, 이차함수는 지수함수보다 빠름
따라서 알고리즘을 주어진 시간내에서 해결하기 위해선 최대한 로그함수내에서 해결하는게 좋고, 그게 불가능하다면, 일차, 이차, 삼차까지 가야함. 지수함수로 가게되면 문제푸는데 굉장히 오랜시간이 걸리므로 지수함수밖에 해결할 수 없는 문제가 아닌이상, 시간초과가 100% 발생