[자료구조] 01 자료구조와 알고리즘 이해 정리

▶

선형구조		비선형구조
	리스트		트리
	스택		그래프
	큐
		단순구조
파일구조			정수
	순차파일		실수
	색인파일		문자
	직접파일		문자열

 

▶성능분석 방법

기준1. 시간 복잡도 : 속도

기준2. 공간 복잡도 : 메모리의 사용량

 

-> 검증이 끝난 알고리즘의 적용을 고려하는 경우 : 속도 기준

-> 특정 알고리즘에 대해서 상대적인 우월성을 입증해야 하는 경우 : 메모리의 사용량 기준

 

 

▶ 데이터의 수 n에 대한 연산횟수의 함수 (T(n) = 핵심연산 횟수)

x축 : 데이터수 / y축 : 연산횟수

 

▶

순차 탐색(Linear Search) : O( n )

: 탐색할 대상을 순서대로 하나씩 핵심연산으로 탐색한다.

 

이진 탐색(Binary Search) : O( log n )

: 탐색할 대상을 반으로 줄여가면서 핵심연산으로 탐색한다.

(가정이 필요하다 예 : 데이터가 정렬되어있다.)

 

 

▶

최악의 경우(Worst Case)

: 탐색이 끝날때까지 데이터가 없는 경우

 

평균적인 경우(Average Case)

: 각 탐색이 끝나는 경우에 동일한 확률의 가중치를 곱하여 계산한다.

-> 이는 동일한 확률이라는 가정에 의해서 성립되고 많은 데이터가 주어지면 시간복잡도를 구하기 어려워진다.

 

 

▶ 빅_오 표기법(Big_Oh Notation)

: 데이터 수의 증가에 따른 연산횟수의 증가 형태를 표현한 것

: 데이터 수의 증가에 따른 연산횟수 증가율의 상한선을 표현한 것

 

쉽게 얘기하면, T(n)에서 가장 영향력이 큰 부분이 어딘가를 따지는 것

-> 다항식인 경우, 최고차항의 차수

(T(n) = 시간 복잡도 함수)

 

O(1)

: 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘

-> 상수형 빅_오

 

O( log n )

: 데이터 수의 증가율에 비해서 연산횟수의 증가율이 매우 낮은 편

-> 로그형 빅_오

 

O( n )

: 데이터의 수와 연산횟수가 비례하는 알고리즘

-> 선형 빅_오

 

O( n*log n )

: 데이터의 수가 2배로 늘 때, 연산횟수는 2배를 조금 넘게 증가하는 알고리즘

-> 선형로그형 빅_오

 

O( n^2 )

: 데이터 수의 제곱에 해당하는 연산횟수 (예를 들어, 중첩 반복문 사용은 바람직하지 못하다.)

-> 데이터 양이 많은 경우 적용하기 무리

 

O( n^3 )

: 데이터 수의 세제곱에 해당하는 연산횟수

-> 적용하기 무리 있는 알고리즘

 

O( 2^n )

: 사용한다는 것 자체가 비현실적인 알고리즘

-> 지수형 빅_오

 

 

▶ 추상 자료형

: Abstract Data Type

: 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열하는 것

 

 

▶ 리스트

: List

: 데이터를 나란히 저장한다.

: 중복된 데이터의 저장을 막지 않는다.

순차 리스트		배열을 기반으로 구현된 리스트
		장점	데이터 참조가 쉽다. 인덱스 값 기준으로 어디든 한 번에 참조가 가능하다.
		단점	배열의 길이가 초기에 결정되어야한다. (변경이 불가능) 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.
연결 리스트		메모리의 동적 할당을 기반으로 구현된 리스트
		종류	단순 연결 리스트, 원형 연결 리스트, 양방향(이중) 연결 리스트