[알고리즘] 시간 복잡도

알고리즘 책을 넘기다 보면

시간 복잡도 란 개념으로 1장 ~ 2장 사이에 위치하고 있어

설명하는 내용도 뭐이리 어렵게 설명하는지

처음으로 알고리즘을 공부해 보겠다는 사람들에게

이런 뷁 ~~ 이란 말이 나오도록

알고리즘이란 어려운 것이야 하는 느낌을 준다 . 

시간복잡도 너 뭐니?

한번 시간 복잡도에 대해서 알아보자 

먼저 시간복잡도를 알기 전에 

 알고리즘을 짠다면 가장 중요한게 뭘가 ?

생각 해보아라

.

.

.

먼저 시간은 적게 걸려야 하고

메모리 사용은 적어야 한다

.

.

이정도 만 생각했다면

당신은 이제 시간 복잡도와 공간복잡도에 대해 다 안것이다.

말 그대로 알고리즘을 구현하는데 있어 

얼마나 속도가 걸리는지

얼마나 적은 메모리 사용하는지 

이자체가 시간복잡도 공간복잡도 라 생각하면된다.

예전 286 시대만 봐도

그 당시 컴퓨터의 사양은 말로 표현 할 수 없었다.

왜냐.. 너무 느려 ㅡ,ㅡ

한마디로 프로세스가 처리하나 하는데 시간이 오래 걸리고

사용하는 공간도 한정적이 던것이다.

그래서 최적의 시간과 아주 작은 메모리 사용만을 추구하던 시대 였기에

시간 복잡도와 공간 복잡도 개념이 지금까지 존속되고 있고

 중요하게 사용되고 있는 것이다.

여기서 그럼 요즘은 컴퓨터가 무지하게 빠른데 

이제 그런거 생각 하지 않아도 되지 않나요?

이런 생각에 빠진다면  

당신은 루저.... ㅡ,.ㅡ

우리가 사용하는 컴퓨터에서는 상관 없지만 

임베디드, 게임, 모바일 분야에서는 시간과 메모리 크기는 생명이다.

이밖에도 매우 중요한 요소이기에 꼭 알아야 한다.

그럼 시간 복잡도에 대해서 알아보자

O(),   ω(),   Θ() 

개념을 알고 가야한다

O() 는 빅오

 ω() 는 오메가

Θ() 는 세타

이렇게 부른다.

이것을 설명하는데 있어 

점근적 상한이니 어려운 표현을 많이 사용하는데

쉽게 말하면

O() 는 최악의 경우

ω() 는 최상의 경우 

Θ() 는 평균의 경우

이정도 개념으로 이해하면 쉬울 것이다.

한마디로 알고리즘은 최악의 경우를 생각하기에 

시간복잡도는 아래와 같다

 

O(1) < O(logn) < O(n) < O(nlogn) < O (n^2) < O(2^n) < O(n^3)

            –O(1)         – 데이터의 크기에 상관없이 일정시간 안에 실행 마침

–O(n)          – 데이터의 크기에 비례하는 시간

–O(n^2)       – n^2에 비례하는 시간이 걸림

–O(log2 n)   – 데이터의 크기에 따라 수행시간이 조금씩 늘어남

–O(nlog2 n) – 입력 자료수가 2배로 늘어나면 수행시간이 2배보다 조금 더 늘어나는 알고리즘

도움이 되었다면 리플을 남겨주세요 ^^