데이터의 표현(데이터의 저장)을 담당하는 것이 자료구조다.
넓은 의미에서 int형 변수도 구조체의 정의 및 배열도 자료구조에 속함.
선형구조--리스트 비선형구조--트리
-스택 -그래프
-큐
파일구조--순차파일 단순구조--정수
-색인파일 -실수
-직접파일 -문자
-문자열
파일도 데이터를 저장하는 도구이기 때문에 파일의 구조도 자료구조에 포함이 된다.
선형구조는 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식이며,
비선형 자료구조는 데이터를 나란히 저장하지 않는 구조이다.
자료구조가 '데이터의 표현 및 저장방법'을 의미한다면
알고리즘은 표현 및 저장 데이터를 대상으로 하는 '문제의 해결 방법'을 뜻한다.
자료구조가 결정되어야 그에 따른 효율적인 알고리즘을 결정할 수 있기 때문이다.
알고리즘은 자료구조에 의존적이다.
속도에 해당하는 알고리즘의 수행시간 분석 결과를 시간 복잡도(time complexity),
메모리 사용량에 대한 분석결과를 공간 복잡도(space complexity)라 한다.
최적의 알고리즘이란 메모리를 적게 쓰고 속도도 빨라야 된다.
일반적으로 알고리즘을 평가할 때는 메모리의 사용량보다 실행속도에 초점을 둔다.
알고리즘의 수행속도를 평가할 때는 연산의 횟수를 n에 대한 연산횟수의 함수 T(n)을 구성한다.
데이터의 수를 함수에 입력하면 연산의 횟수가 바로 계산이 되는 식을 구성한다는 뜻인데
식을 구성하면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있다.
알고리즘 시간 복잡도를 계산하기 위해서는 핵심이 되는 연산이 무엇인지 잘 판단하고 그 연산을 중심으로 시간 복잡도를 계산해야 한다.
알고리즘의 성능을 판단하는데 있어서 중요한 것은 '최악의 경우'이다.
평균적인 경우는 시간 복잡도를 평가하는 정보로 의미를 지닌다.
이진 탐색 알고리즘을 적용하기 위해서는 배열에 저장된 데이터는 정렬되어 있어야 한다.
T(n)이 다항식으로 표현이 된 경우, 최고차항의 차수가 빅-오가 된다.
빅오는 데이터 수의 증가에 따른 연산횟수의 증가 형태를 나타내는 표기법이다.
대표적인 빅-오
O(1)
데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘.
O(logn)
데이터 수의 증가율에 비해 연산횟수의 증가율이 훨씬 낮은 알고리즘.
참고로 바람직한 유형이다.
O(n)
선형 빅-오. 데이터의 수와 연산횟수가 비례하는 알고리즘.
O(nlogn)
선형로그형 빅-오. 데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘을 의미.
O(n^2)
데이터의 수의 두배에 해당하는 연산횟수를 요구하는 알고리즘을 의미.
데이터의 양이 많은 경우에는 적용하기가 부적절한데, 이는 이중으로 중첩된 반복문 내에서 알고리즘에 관련 된 연산이
진행되는 경우에 발생한다. 중첩된 반복문의 사용은 알고리즘 디자인에서 그리 바람직하지 못하다.
O(n^3)
데이터 수의 세 배에 해당하는 연산횟수를 요구하는 알고리즘을 의미.
이는 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행된 경우에 발생한다.
이 역시 그냥 적용하기에는 무리가 있는 알고리즘.
O(2^n)
지수형 빅오. 이는 사용하기에 매우 무리가 있는, 사용한다는 것 자체가 비현실적인 알고리즘이다.
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n>=K에 대하여 f(n)<=Cg(n)을 만족하는 두 개의 상수 C와 K가 존재하면
f(n)의 빅-오는 O(g(n))이다.
