자료 구조

자료 구조

 

자료구조란 무엇인가?

        자료구조 : 프로그램이란 데이터를 표현 및 저장하는 것이다.

        알고리즘 : 표현된 데이터를 처리하는 것이다.

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

 

자료구조 분류

        선형 자료구조 : 리스트, 스택, 큐

        비선형 자료구조 : 트리, 그래프

 

알고리즘의 성능분석 방법

        시간 복잡도 : 얼마나 빠른지를 비교

        공간 복잡도 : 얼마나 메모리를 적게 쓰는지 비교

 

        *빅-오 표기법 : 데이터의 수의 증가에 따른 연산횟수의 증가 형태를 표현한 것

                대표적인 빅오

                -O(1) 상수형 빅-오

                -O(log n) 로그형 빅-오

                -O(n) 선형 빅-오

                -O(nlog n) 선형로그형 빅-오

                -O(n^2) 데이터의 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘

                -O(n^3) 데이터의 수의 세제곱에 해당하는 연산횟수를 요구하는 알고리즘

                -O(2^n) 지수형 빅-오

 

                빅-오의 성능

                O(1) < O(log n) < O(n)  < O(nlog n)  < O(n^2) < O(n^3) < O(2^n) 

                *빅-오 표기가 작을 수록 좋은 알고리즘이다.

 

 

 

 

출처 : 윤성의 열혈 자료구조