[알고리즘]01.알고리즘의 효율성

컴퓨터 공학 알고리즘 이란?

해결하려는 문제가 있고, 컴퓨터로 구현 가능한 것

예를 들어 1+1의 문제가 있다면 답 2를 만들기 위한 문제 풀이를 컴퓨터로 구현한다면,

1+1이라는 문제를 해결하는 알고리즘을 구현한 것이다.

흔히 알고리즘이라 생각하는 것들

• 상기 1+1과 같은 쉬운 코드는 실무에서는 알고리즘이라 부르지 않음
• 그렇다고 명확한 기준이 존재하지 않음
• 하지만 알고리즘 책이나 위키 피디 등 공신력 있는 곳에 실린 것들은 확실히 알고리즘이라고 부르고 있음

훌륭한 알고리즘이란?

1. 입력과 출력이 명확하다. (단, 입력은 빈 값일 수 있다.)
2. 문제 풀이 단계가 명확하며, 모호하지 않는다.
3. 유한 시간 안에 결과가 도출되어야 한다.
4. 포팅이 어려운 해결법은 피한다. ( 예를 들어 특정 언어에서 지원하는 특정 API를 사용하여 풀이)
5. 같은 문제를 푸는 다양한 방법 중에 가장 효율 적임 ( 시간 복잡도, 공간 복잡도 등을 따짐)

알고리즘의 효율성

• 자원을 효율적으로 사용한다.
  • CPU 속도, 메모리 사용량 등
• 시간과 공간은 종종 상반 관계를 가진다.
• 자원을 많이 사용할수록 그 알고리즘이 복잡할 가능성이 높다.
  • 시간 복잡도 ( time complexity)
  • 공간 복잡도 ( space complexity)
  • 알고리즘 복잡도를 표현하는 방법 중 하나 : 빅오 (Big - O) 표기법

알고리즘의 효율성 분석은 다소 추상적

알고리즘 공부를 할 때는 하드웨어 차이는 신경 쓰지 않는다. 그러므로 알고리즘 자체에 집중이 가능하다.

즉, RAM( random - access machine , 랜덤 접근 기계 [메모리 RAM을 뜻하는게 아님]) 를 사용한다는 전제로 알고리즘 풀이를 한다.

• 가상의 기계
• 레지스터를 갖춘 CPU 1개
• 메모리 간접 참조 (indirection) 지원
• 캐시 메모리 혹은 가상 메모리 등은 없음

그러므로 실제 코드 실행 속도는 하드웨어 따라 매우 달라질 수 있음