자료구조란, 그리고 알고리즘

Data -> 저장공간 + 읽기/쓰기/삽입/삭제/탐색(연산)

 

자료구조란 => 컴퓨터에서 자료를 효율적으로 관리하고 구조화시키는 방법

ex) 변수(Variable), 배열(Array), List 등

 

인류최초의 알고리즘은 최대공약수(GCD)계산 알고리즘 이다.

 

알고리즘 수행시간: 최악의 입력에 대한 기본연산 횟수 T(n)

 

알고리즘 시간 복잡도를 계산할때 크게 두가지 방법이 있는데,

1. 모든 입력에 대해 기본연산 횟수를 더한 후 평균 => 정확한 방법이지만 현실적으로 불가능하다.

2. worst case 입력에 대한 기본연산 횟수를 측정한다. => 어떤 입력에 대해서도 이보다 수행시간이 크지 않음(적합)

 

ex) T1(n) = 2n-1 , T2(n)=4n+1, T3(n)=2n^2-3n일때,  T2가 T1보다 2배 빠르다고 할 수 있으며,        T1(n) => O(n)     T2(n) => O(n)   T3(n)=>O(n^2) 이다.  또 T(6) 같은 경우 O(1) (상수시간) 이 걸린다고 할 수 있다.