알고리즘이, 좋은 알고리즘이 뭐냐고 물어보면 뭐라고 대답할래?

 

알고리즘?

문제를 해결하기 위한 절차

조금 더 풀어보면, 알고리즘은 일단 문제가 존재해야 한다. 그리고 해결을 해야한다는 목적을 가지고 있을 때, 알고리즘은 문제를 해결하는 절차를 이야기한다.

알고리즘의 조건

1. 항상 올바른 답을 낼 것. = 답을 내야 한다
2. 유한한 시간 안에 종료될 것. = 끝나야 한다

좋은 알고리즘의 요소

• 자원을 효유적으로 쓰는 // ↔ 메모리 초과
• 이해하기 쉬운 (간결한) // ↔ 스파게티 코드
• 속도가 빠른 // ↔ 시간 초과

 

모든 요소를 충족하는 것은 어렵다.

이 중에서 가장 중요한 요소는 바로 속도이다.

Big-O 표기법

영어는 어렵다. 수식은 어렵다. 영어 수식은 어렵다 ㅎㅎㅎㅎ

매번 보지만 이해하기 어렵다. 쉽게 이해해보겠다.

쉬운 말로 풀어 해석해보면,

f(n) = Ο(g(n)) 이라는 것은, 적당히 큰 x에 대해서 대충 f(x)보다 g(x)이 크다는 의미이다.

• 적당히 큰 수에 대해서는 f(n)의 증가량이 g(n)의 증가량을 넘지 않는다.
• 대략적인 f(n)의 상한을 알 수 있다.
• 서로 다른 알고리즘의 시간 복잡도를 쉽게 비교할 수 있다.