복습 - 자료구조 / 알고리즘

자료구조와 알고리즘

1. 자료구조

• 자료(Data)의 집합을 의미
• 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것
• 유한한 형태

2. 알고리즘

• 문제를 해결하기 위한 절차적인 과정
• 무한한 형태

• 자료구조와 알고리즘은 서로간의 영향을 많이 받음
• 하드웨어 가까울 수록 중요도가 높아짐
• 소프트웨어일 수록 중요도가 떨어짐 (지도, 검색 서비스는 제외)

3. 시간복잡도 / 공간복잡도

• 시간/공간복잡도는 사용자마다 환경이 다르기때문에 절대적인 기준을 비교할 수 없음
• 단순 시간, 공간을 계산함
• 시간/공간복잡도는 Big-O 표기법을 사용

4. Big-0표기법

※ Big-O 표기법에서 사용되는 표기법

입력이 증가 할때 처리시간이 증가하는 정도
좋은 알고리즘이란 복잡도를 낮추는 행위

시간 복잡도의 성능 비교

Fast - O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) - Slower

Big-O표기법 예제

1. O(1) : 스택에서 push, pop
2. O(log n) : 이진트리
3. O(n) : for 문
4. O(n log n) : 퀵 정렬, 병합정렬, 힙 정렬
5. O(n2) : 이중 for문, 삽입정렬, 거품정렬, 선택정렬
6. O(2n) : 파보나치 수열