🤓 What I Learned Today

(참고서적)

알고리즘

매일 알고리즘을 풀지만 알고리즘에 대한 정의는 제대로 알아보지 않았다. 알고리즘이란 문제,목적을 달성하기 위해 여러 과정을 거치게 되는데 당연히 효율적이고 사용 환경에 최적인 알고리즘을 선택하여 풀어야한다.

알고리즘 시간은 코드를 실행하는 속도에 의존하는데 이 속도는 컴퓨터의 처리속도, 언어 종류, 컴파일러 속도에 따라 달려있다.

여기서 어제 배운 복잡도가 나오는데 알고리즘의 성능 분석은 실행에 필요한 공간 측면에서 분석하는 공간 복잡도와 실행 소요시간 측면에서 분석하는 시간 복잡도를 추정하여 평가한다. 따라서 시간 복잡도가 낮은 알고리즘을 선택하여 사용한다.

---

빅오표기법

알고리즘 성능을 수학적으로 표기해주는 표기법으로 알고리즘의 데이터나 사용자 증가률에 따른 알고리즘 성능을 예측하는게 목표여서 중요하지 않은 부분인 상수와 같은 숫자는 모두 제거한다. 즉, 불필요한 연산을 제거하고 알고리즘 분석을 쉽게 할 목적으로 사용된다. 알고리즘이 해당 차수이거나 그보다 낮은 차수의 시간복잡도를 가진다는 의미이기도 한다.

여기서 측정되는 복잡성에는 시간 복잡도와 공간 복잡도가 있다.

• 시간 복잡도: 입력되는 n의 크기에 따라 실행되는 조작의 수
• 공간 복잡도: 알고리즘이 실행될 때 사용하는 메모리 양