1. Understanding of Datastructure and Algorithm

개요

자료구조란?

자료, 즉 데이터를 효율적으로 저장하고 관리하기 위한 구조를 말합니다.

자료구조의 분류

선형구조

• 리스트

• 스택

• 큐

비선형구조

• 트리

• 그래프

파일구조

• 순차파일

• 색인파일

• 직접파일

단순구조

• 정수

• 실수

• 문자

• 문자열

알고리즘의 성능분석 방법

시간 복잡도, 공간 복잡도

시간 복잡도

알고리즘의 수행시간에 대한 분석결과를 말합니다.

공간 복잡도

메모리 사용량에 대한 분석결과를 말합니다.

💡

일반적으로 알고리즘의 성능은 시간 복잡도를 말합니다.

시간 복잡도 분석의 핵심 요소

알고리즘의 핵심이 되는 연산을 파악하고, 그 연산을 중심으로 시간 복잡도를 분석합니다.

빅-오(Big-O) 표기법

최고차항의 차수로 시간 복잡도를 표기하는 방법을 말합니다.

대표적인 Big-O

$O(1)$

• 상수형 빅-오

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

$O(log\ n)$

• 로그형 빅-오

• 데이터 수의 증가율에 비해 연산횟수의 증가율이 훨씬 낮은 유형의 알고리즘

• 이진 탐색

$O(n)$

• 선형 빅-오

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

$O(n\ log\ n)$

• 선형로그 빅-오

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

$O(n^2)$

• 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘

• 이중 for 문

$O(n^3)$

• 데이터 수의 세제곱에 해당하는 연산횟수를 요구하는 알고리즘

• 삼중 for 문

$O(2^n)$

• 지수형 빅-오

• 매우 매우 매우 매우 매우 안 좋은 알고리즘

Uploaded by Notion2Tistory v1.1.0