[Algorithm 이론] 알고리즘이란? | (ft. 표현 방법, 성능 분석, Time Complexity, Big-O)

알고리즘에 대한 개념 정리, 알고리즘 성능 평가 방법 (time complexity, Big-O, etc.)

알고리즘이란?

알고리즘(Algorithm)이란?

“유한한 절차적 단계를 통해 문제를 해결하기 위한 절차나 방법”

즉, 정의된 작업을 순차적으로 진행하는데 (영겁의 시간을 기다리지 않고) 최대한 빨리 끝나면 좋다.

CS domain : 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법
정리: 어떤 문제를 해결하기 위한 절차(process)

EXAMPLE : 1부터 100까지의 합을 구하는 문제.

(sol1) 무작정 순서대로 더하기

$1+2+3+\cdots+100 =5,050$

(sol2) 피보나치의 방법?

$(1+100)+(2+99)+\cdots+(50+51) = 50 \times 101 = 5,050$

(sol2) 처럼 간지나는 절차로 문제를 풀이하는 방식이 좋은 알고리즘이다.

알고리즘 표현법

pseudo code (슈도코드, 의사코드)
flow chart (순서도, 흐름도)

Pseudo code: 일반적인 언어로 코드를 흉내내어 알고리즘을 써 놓은 코드.

def calcSum(n):
	sum = 0 
	for i in range(1, n+1):
		sum += i 
	return sum 

print(calcSum(100))

(작동하는 코드인것 처럼) 흉내만 내는 코드
실제적인 프로그래밍 코드처럼 컴퓨터에서 실행할 수 없음 (왜? 특정 언어의 문법을 따르지 않아서)

Flow chart: 프로그램이나 작업의 진행 흐름을 순서에 따라 여러가지 기호나 문자로 나타낸 도표

프로그램의 논리적인 흐름, 데이터의 처리 과정을 표현하는 데 활용
(프로그램을 작성하기 전) 프로그램의 전체적인 흐름과 과정 파악을 위해 필수적으로 거쳐야 되는 작업

무엇이 좋은 알고리즘인가 (1) (성능 분석)

주요 지표(metrics)

정확성 (accuracy) - 시킨대로 얼마나 잘하나?
작업량(=연산량) (operation) - 적은 연산으로 원하는 결과를 얻어내는가?
메모리 사용량 (memory) - 알고리즘 동작에 메모리가 얼마나 필요한가?
단순성 (simplicity) - 간단 명료한 정도
최적성 (optimality) - 알고리즘이 더 이상 개선할 여지 없이 최적화되었나?

EXAMPLE: 알고리즘 성능 분석

1~100 까지의 합을 구하는 아래 두 알고리즘의 성능을 ‘작업량을 비교’하여 분석하시오.

(A1) 단순 순서대로 합

$1+2+3+\cdots + 100 = 5,050$

99번의 연산 (덧셈 99번)
숫자가 늘어날 수록 연상 횟수도 (선형적으로) 늘어남

(A2) 피보나치 방법

$\{100\times(1+100)\}\div2=5,050$

3번의 연산 (덧셈 1회, 곱셈 1회, 나눗셈 1회)
숫자가 늘어나도 연산 횟수는 일정함

‘(A2)의 작업량이 < (A1)의 작업량’ 이므로 (A2)가 더 좋은 알고리즘이다.

무엇이 좋은 알고리즘인가 (2) (Time Complexity, 시간 복잡성)

‘알고리즘 작업량’을 표현하기 위해 time complexity 개념을 사용한다.

시간 측정 방법:

(방법1) 실제 걸리는 시간을 측정

컴퓨팅 환경에 따라 달라질 수 있음(e.g., CPU vs. GPU)

(방법2) 실행되는 명령문의 개수(operations)를 계산

(방법1) 보다 좀더 일반적인 계산 방법

EXAMPLE: 알고리즘 시간 복잡도 계산

‘실행되는 명령문의 개수를 계산’하여 위에서 푼 (A1) (A2) 두 알고리즘의 ‘시간 복잡도’를 측정하시오.

(A1) 단순 순서대로 합

def calcSum(n): 
	sum = 0  # 1회 
	for i in range(1, n+1): # 1회 
		sum += i  # 1회 
	return sum

실행되는 명령문 개수 = $1 + input*2=1 + 루프횟수*2=1 + n*2 = 2n+1$

(A2) 피보나치 방법

def calcSum(n): 
	return n *(1+n) // 2   # 3회

실행되는 명령문 개수 = $곱셈1회+덧셈1회+나눗셈1회 = 3회$

(A1)는 입력 $n$ 의 크기에 따라 실행되는 명령문의 개수가 선형적(linearly)으로 증가한다.

반면에, (A2) 는 입력의 크기가 증가해도 항상 실행되는 명령문의 개수는 3개 이다.

따라서, (A2) 알고리즘이 Time Complexity 관점에서도 좋은 알고리즘이다.

Time Complexity ≒ Big-O 표기법

시간 복잡도 함수 중에서 가장 큰 영향력을 주는 $n$ 에 대한 항(=최고차항)만을 표시
계수(Coefficient)는 생략하여 표시
상수값(Constant)인 경우 1로 표시

EXAMPLE: 빅-오(O) 표기법)

$O(2n+1)=O(2n)=O(n)$

$2n+1$ 에서 최고차 항( $2n$ )만 선택
다시, 계수 $2$ 를 제거 ; $O(n)$ 으로 표기한다

$O(2n^2+10n+100) = O(2n^2)=O(n^2)$

$O(4) = O(4\times1) = O(1)$

※ 입력값의 최고차항만 남겨서 표현하는 이유는?

알고리즘에 가장 큰 영향을 주는 요소만을 가지고 Time Complexity를 간략히 표현하기 위해서.

Big-O 표기법의 특징

요소 수( $n$ )가 증가함에 따라 각기 다른 시간복잡도의 알고리즘은 아래와 같은 연산 횟수를 가짐.

big-o
https://velog.io/@heyday_7/Big-O-Notation

$n^2$ , $2^n$ , $n!$ 같은 연산 횟수를 가지는 알고리즘은 요수 수에 따라 연산수가 기하학적(exponentially)으로 증가하므로 사용에 유의할 것

어떤 알고리즘을 선택하시겠습니까?

같은 문제를 해결한 두 알고리즘 중 서비스를 위해 어떤 알고리즘을 선택해야 할까?

A 알고리즘	B 알고리즘
시간 복잡도 $logN$	시간 복잡도 $N^2$

직관적인 실제 예시를 들어보자.

대한 민국 인구에 대해 정보 조회하는 프로그램이 N=10 일 때,

A 프로그램	B 프로그램
1초	100초

A 프로그램이 1초로 시간복잡도가 낮기 때문에 당연히 A프로그램을 선택한다.

Summary

알고리즘의 정의
알고리즘 표현 방법 (pseudo code, flow chart)
알고리즘 성능 평가(1)
알고리즘 성능 평가(2) (ft. time complexity)
Big-O 표기법
어떤 알고리즘을 선택할 것인가? (작업량이 작은 것, time complexity가 작은 것)

Search

컴돌이 도란뇽's AI 스터디 노트