알고리즘과 시간 복잡도

🚀 알고리즘

계산이나 작업을 하기 위한 순서

 

📌 알고리즘과 프로그램

 

프로그램은 완성된 건물이라면 알고리즘은 건물의 뼈대에 해당한다.

 

📌 알고리즘 설계

컴퓨터는 기본 명령들(덧셈, 데이터 저장) 등을 조합하여 동작한다.

컴퓨터가 실행할 수 있는 기본 명령만 가지고 조합하여 알고리즘을 구현하도록 하는 것이 알고리즘 설계이다.

 

📌 알고리즘 선택 방법

알고리즘을 선택하는 기준에는 정확도, 메모리 사용량, 시간 복잡도 등이 있지만 일반적으로 시간 복잡도를 가장 중요시 여긴다.

 

⏰ 시간 복잡도

시간 복잡도는 코드를 실행하고 결론을 도출하는 데 까지 걸리는 시간을 의미한다.

*사용하는 언어, 컴퓨터의 처리 속도 등에 의존한다.

 

📌 계산 방법

주로 '프로세스를 종료하기 까지 기본 단위를 몇회 실행하는가' 로 계산 시간을 측정한다.

선택정렬
1. 수열에서 최솟값을 찾는다.
2. 최솟값을 수열의 가장 왼쪽 숫자와 교환한다.

선택 정렬을 예로 들면 1번과 2번을 결과가 나올 때 까지 반복한다.

이때 이 과정을 몇번 수행하는 지 검수한다.

 

📌 BIG O 표기법

O는 '중요한 항목 이외에는 무시한다' 라는 의미를 가진다.

때문에 O( )의 형식의 시간 복잡도에서 괄호() 안의 수식은 시간에 가장 많은 영향을 주는 요소만을 간추려서 나타낸다.

선택정렬의 시간 복잡도(O(n^2))는 전체 수식 중 실행시간에 가장 많은 영향을 주는 N^2만을 표기한다.

Big O표기법에서 자주 사용되는 시간 복잡도 이다.

표기에 따라 직관적으로 대소관계를 이해하는 것이 도움이 된다.