자료구조튜터링-1.자료구조와알고리즘

소프트웨어의 개발

자료구조

자료를 정리하는 방법

프로그램: 자료구조 + 알고리즘

int main(void){
	int a = 3;
    int b = 5;
    int result = a + b;
}
자료구조=자료: a, b, result
알고리즘: +, 모든 단계적인 절차

알고리즘의 기술방법

1. 자연어
2. 흐름도
3. 수도코드
4. 프로그래밍 언어

알고리즘의 성능분석

시간복잡도

공간복잡도

int main(void){
    int a[n] = {1, 2, 3}, sum = 0;
    for(int i = 0; i < n; i++){
    	sum += a[i];
    }
}

시간복잡도 = 중요한 연산의 횟수 = n - 1
공간복잡도 = 메모리에 n만큼 정수 저장 = n + 2

차수표기법

빅오표기법

상한
정의: 모든 n>n0에 대하여 f(n) <= c*g(n)을 만족하는 n0와 c가 존재하면
f(n) ∈ O(g(n))
2n + 1 < 10n => ∈ O(n)
2n + 1 < n^2 => ∈ O(n^2)

빅오메가 표기법

하한
정의: 모든 n>n0에 대하여 f(n) >= c*g(n)을 만족하는 n0와 c가 존재하면
f(n) ∈ O(g(n))
2n + 1 > n => ∈ 오메가(n)
2n + 1 > 1 => ∈ 오메가(1)

빅세타표기법

상한 & 하한
정의: 모든 n>n0에 대하여 c1g(n) >= f(n) >= c2g(n)을 만족하는 n0와 c가 존재하면
3n > 2n + 1 > n => ∈ 세타(n)