What is Algorithm?

이 글은 책 알고리즘 도감에서 알고리즘 기본 부분을 정리한 글입니다.

 

Algorithm

What is Algorithm?

알고리즘은 계산이나 작업을 하기 위한 순서이다.

IT관점에서는 특정 문제를 컴퓨터로 해결하기 위한 순서가 알고리즘이다.

 

계산 시간

같은 알고리즘을 사용하더라도 컴퓨터의 성능에 따라 시간이 달라진다.

따라서 계산 시간은 스텝 수를 활용한다.

계산을 종료하기까지 기본 스텝을 몇 회 실행했는가?

Example. 선택 정렬 시간 구하기, 수열의 숫자 개수(n)
1) 수열에서 최솟값을 찾는다
2) 최솟값을 수열의 가장 왼쪽 숫자와 교환 -> 다시 1번으로!

Explain.
1) '하나의 숫자를 확인한다' -> 기본 단위 -> 걸리는 시간 T1
2) 1번 동작 걸리는 시간 -> n*T1
3) '두개의 숫자를 교환한다' -> 걸리는 시간 T2
4) 총 시간 -> (n*T1 + T2) + ((n-1)*T1 + T2) ... (1*T1 + T2)
            = 1/2n(n+1)*T1 + n*T2 = 1/2*T1*n² + (1/2*T1 + T2)n

계산 시간 표현 방법

• Big-O 표기법
  • '중요한 항목 이외는 무시한다' 라는 의미를 가지는 기호 => 불필요한 연산 제거
  • 위 선택 정렬 예시에서 가장 영향이 큰 항목이 n²이므로 계산 시간은 O(n²)로 표현

출처 : https://blog.chulgil.me/algorithm/

Big-O	시간	설명
O(1)	상수 시간	오직 한 단계만 처리함
O(log n)	로그 시간	연산마다 특정 요인에 의해 줄어듬
O(n)	직선적 시간	단계의 수와 입력 값이 1:1 관계를 가짐
O(nlogn)	선형로그형	단계의 수가 N*(log2N)번 만큼의 수행시간을 가짐
O(n²)	2차 시간	입력값의 n의 제곱
O(C^n)	지수 시간	주어진 상수값 C의 n 제곱

[참고사이트]

알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기