알고리즘을 좋아하는 나

알고리즘 스터디 자료를 준비중에 ADT라는 용어를 접했다.

ADT는 Abstract-Data-Type이다.

말 그대로 추상 자료형.

Wallet이라는 자료형을 선언했다.

그 Wallet을 기반으로 연산의 종류가 있을것이다.

그것도 자료형 정의의 일부다.

자료의 ADT는

기능들이다.

기능들 말고도 구조체의 정의도 넣을 수 있다.

근데 ADT에는 필요한 정보들만 넣는것이 좋다.

리스트

• 순차 리스트
• 연결 리스트

둘의 ADT가 같을 수 있다.

ADT에 표준은 없다.

생각은 모두 자유롭게 할 수있고, 그것을 코드로 옮길 수 있다.

위 둘의 리스트의 공통점은

선형구조다.

프로그램이란?

프로그램은 데이터를 표현하고 처리하는 것이다.

자료구조란?

데이터의 표현 및 저장방법

자료구조는 기본적으로 다움과 같이 분류할 수 있다.

선형구조

리스트    

스택

큐

비선형구조

트리

그래프

파일구조

순차파일

색인파일

직접파일

단순구조

정수

실수

문자열

문자

파일도 데이터를 저장하는 도구이기 때문에 자료구조에 포함된다.

선형구조

데이터가 선처럼 쭉 이어져 있다.

비선형구조

데이터가 나란히 있지 않다.

자료구조에 따라 알고리즘은 바뀐다.

알고리즘은 자료구조에 의존적이다.

알고리즘의 성능

시간복잡도

실행 시간

공간복잡도

메모리 사용

best case

운이 좋을때

worst case //거의 이거로 분석한다

운이 안좋을때

계산방법 T(n)=n  

T는 함수, (n)는 자료개수

average case

평균적으로

바이너리

두 조각

Big-Oh Notation 표기법

최고차항