(2) 알고리즘
1) 알고리즘의 정의
[1]컴퓨터로 문제를 풀기 위한 단계적인 절차이며, 특정 작업을 수행하기 위한 명령어들의 집합이다.
[2] 특정한 일을 수행하는 명령어들의 유한 집합이다.
[3] 프로그램 = 자료구조 + 알고리즘
ex) 최대값 탐색 프로그램 = 배열 + 순차탐색
2) 알고릐즘의 조건
[1] 입력 : 외부에서 제공되는 데이터가 0개 이상 있다.
[2] 출력 : 적어도 하나의 결과를 생성한다.
[3] 명확성 : 알고리즘을 구성하는 각 명령어들은 그 의미가 명백하고 모호하지 않아야 한다.
[4] 유한성 : 알고리즘의 명령대로 순차적인 실행을 하면 언젠가는 반드시 실행이 종료되어야 한다.
[5] 유효성 : 원칙적으로 모든 명령들은 조잉와 연필만으로 수행될 수 있게 기본적이어야 하며, 반드시 실행 가능해야 한다. (원칙적으로 모든 명령들은 오류가 없이 실행 가능해야 한다.)
(3) 복잡도
1) 프로그램의 공간 복잡도(space complexity)
[1] 프로그램을 실행시켜 완료하는 데 필요한 총 저장 공간을 말한다.
[2] 고정 공간 : 프로그램의 크기가 입출력의 횟수에 관계없이 고정적으로 필요한 저장공간을 의미한다.
[3] 가변 공간 : 실행 과정에서 데이터 구조와 변수들이 필요로 하는 저장 공간이다.
[4] 공간 복잡도 = 고정 공간 + 가변 공간
2) 프로그램의 시간 복잡도(time complexity)
[1] 프로그램을 실행시켜 완료하는 데 걸리는 시간을 의미한다.
[2] 컴파일 시간 : 소스 프로그램을 컴파일하는데 걸리는 시간으로서 프로그램의 실행특성에 의존하지않기 때문에 고정적이다.
[3] 실행 시간 : 프로그램의 실행시간을 추정하기 위해서는 하나의 단위 명령문 하나를 실행하는데걸리는 시간과 실행 빈도수가 있어야 한다.
[4] 시간 복잡도 = 컴파일 시간 + 실행 시간
[연산 시간 그룹]
- 상수시간 : O(1)
- 로그시간 : O(logn)
- 선형시간 : O(n)
- n로그시간 : O(nlogn)
- 평방시간 : O(n^2)
- 입방시간 : O(n^3)
- 지수시간 : O(2^n)
- 계승시간 : O(n!)
[연산 시간의 크기 순서]
O(1) < O(logn) < O(n) < O(nlogn) < O(N^2) < O(2^n) < O(n!) < O(n^n)
3) 점근적 표기법
[1] 빅오(Big-oh) 표기법의 수학적 정의
n>= n0를 만족하는 모든 n에 대하여 f(n) <= c*g(n) 인 조건을 만족하는 2개의 양의 상수 c와 n0가 존재하기만 하면 f(n) = O(g(n))이다.
[2] 오메가(Omega) 표기법의 수학적 정의
n>= n0를 만족하는 모든 n에 대하여 f(n) >= c*g(n) 인 조건을 만족하는 2개의 양의 상수 c와 n0가 존재하기만 하면 f(n) = Ω(g(n))이다.
[3] 세타(Theta) 표기법의 수학적 정의
n>= n0를 만족하는 모든 n에 대하여 c1g(n) <= f(n) <= c2g(n) 인 조건을 만족하는 3개의 양의 상수 c1, c2와 n0가 존재하기만 하면 f(n) = θ(g(n))이다.
[정렬 알고리즘의 복잡도]
| 정렬종류 | 평균 | 최악 |
|---|---|---|
| ⭐️버블정렬 | O(n^2) | O(n^2) |
| ⭐️선택정렬 | O(n^2) | O(n^2) |
| ⭐️삽입정렬 | O(n^2) | O(n^2) |
| 쉘정렬 | O(n^2) | O(n^2) |
| 퀵정렬 | O(nlogn) | O(n^2) |
| 2-way merge 정렬 (합병정렬) | O(nlogn) | O(nlogn) |
| 힙정렬 | O(nlogn) | O(nlogn) |
2. 논리 데이터저장소
(1) 논리 데이터 모델링
- 사용자들의 요구 사항을 분석하여 DB에 저장될 정보를 파악하고, 필요한 정보들 간의 연관 관계를 모형화하는 과정이다.
[1] 데이터 모델링 절차
⭐️ 개념적 설계 -> 논리적 설계 -> 물리적 설계
[ㄱ] 개념적 모델링
- 사용자들의 요구사항을 이해하기 쉬운 형식으로 간단히 기술하는 단계.
- 개념 스키마 모델링과 트랜잭션 모델링을 병행적으로 수행
- 개념 스키마 모델링 : 데이터의 조직과 표현을 중심으로 한 데이터 중심 설계
- 트랜잭션 모델링(처리, 흐름 중심 설계) : 응용을 위한 데이터 처리에 주안점을 둔 처리 중심 설계
[ㄴ] 논리적 모델링
- 개념적 설계에서 만들어진 구조를 구현 가능한 data 모델로 변환하는 단계.
- 논리적 데이터 모델링은 목표하는 DBMS가 구현되어 있는 환경과 특성까지는 고려하지 않고 해당 DBMS가 지원하는 데이터 모델에 적합하게 변환한다. 즉, DBMS에 종속적이라 할 수 있다.
- 논리적 설계 단계는 앞 단계의 개념적 설계 단계에서 만들어진 정보 구조로부터 목표 DBMS가 처리할 수 있는 스키마를 생성한다. 이 스키마는 요구 조건 명세를 만족해야되고, 무결성과 일관성 제약 조건도 만족하여야 한다.
[ㄹ] 물리적 모델링
- 논리적 데이터베이스 구조를 내부 저장 장치 구조와 접근 경로 등을 설계.
- 물리적 데이터베이스의 기본적인 데이터 단위는 저장 레코드이다.
- 파일이 동일한 타입의 저장 레코드 집합이라면, 물리적 데이터베이스는 여러 가지 타입의 저장레코드 집합이라는 면에서 단순한 파일과 다르다.
- 물리적 데이터베이스 구조는 데이터베이스에 포함될 여러 파일 타입에 대한 저장 레코드의 양식, 순서, 접근 경로, 저장 공간의 할당 등을 기술한다.
[ㅁ] 데이터베이스 구현
(2) 논리 데이터저장소
[1] 논리 데이터 모델링과 관련하여 데이터 구조로 만들어진 데이터 저장소이다.
[2] 데이터베이스의 논리적 구성
- 개체(entity) : 표현하려는 우형, 무형의 정보의 대상으로 존재하면서 서로 구별이 되는 것으로, 하나이상의 속성으로 구성된다.
- 속성(attribute) : 개체의 특성이나 상태를 기술하는 것이다.(단독으로 존재하기는 어렵다.)
- 관계(relationship) : 개체간 또는 속성간의 상호 작용. (1:1, 1:n, n:m)
(3) 논리적 저장 구조(오라클)
[1] Tablespace : 논리적으로 서로 관련된 데이터가 저장된 파일들을 묶어놓은 단위로 물리적인 파일과 논리적인 저장단위를 서로 분리시키는 역활을 한다.
[2] Segment : Tablespace 내에 특정 유형의 논리적 저장구조로 할당된 영역이고 테이블, 인덱스등의 오브젝트가 세그먼트에 포함된다.
[3] Extent : 하나 이상의 연속된 데이터 블록의 모임이고 Segment에 대한 공간 할당 단위이다.
[4] Block : 오라클의 기본 입출력 단위이다.
