Processing math: 100%

본문 바로가기

강의노트/자료구조론

(3)

[자료구조론] 2주차: 순환 순환(Recursion) 정의 자체가 순환적인 경우 적합하다. 주어진 문제를 더 작은 동일한 문제로 분할해 해결(분할 정복: Divide and Conquer) Ex) Factorial

$n!$ 은

$n \geq 1$ 에 대해서는

$n(n-1)!$ ,

$n = 0$ 에 대해서는 1로 정의할 수 있다. 1 2 3 4 int factorial(int n) { return (n

$O(n)$ 순환의 경우 대략

$x^n$ 에 대해

$n=2^k$ 라 하면

$k$ 번의 계산 필요 즉

$\log_{2}{n}$ 번의 연산을 요하므로

$O(\log{n})$ 1 2 3 4 5 6 7 8 9 10 int power(int x, int n) { if (n == 0) return 1; else { return (n % 2 == 0) ? pow..

[자료구조론] 2주차: Notation Big-O notation 입력의 개수

$n$ 에 따른 함수의 상한을 표시한 것 수학적 정의 두 함수

$f(n)$ 과

$g(n)$ 이 주어졌을 때, 모든

$n \geq n_0$ 에 대해

$\mid f(n)\mid\; \leq \; c\mid g(n) \mid$ 을 만족하는 상수

$c$ ,

$n_0$ 가 존재하면

$f(n) = O(g(n))$ 이다.

$n$ 이 어느 정도 커졌을 때

$f(n)$ 이

$g(n)$ 보다 항상 작으면

$g(n)$ 은

$f(n)$ 보다 연산 횟수가 큰 상한이라는 얘기다. 기본 연산 횟수가 다항식일 경우 최고차항만 사용

$8n^2\log{n} + 5n^2 + n$ ->

$O(n^2\log{n})$

$10$ ->

$O(1)$ $O(1) < O(\log{n}) < O(n) < O(n\log{n}) < O(..

[자료구조론] 1주차 자료구조(Data structure): 컴퓨터에서 데이터를 보관하는 구조 알고리즘(Algorithm): 주어진 문제를 풀기 위한 단계적인 절차(procedure) 프로그램 = 자료구조 + 알고리즘 문제 해결을 위해 적절한 자료구조를 선택하고, 이 자료구조를 사용하는 효율적인 알고리즘 작성이 필요하다. 알고리즘의 조건 입력과 출력: 입력은 없어도 되지만 출력은 반드시 존재해야 한다. 명백성(Definiteness): 모든 명령어는 모호해서는 안 된다. 유한성(Finiteness): 반드시 종료되어야 한다. 유효성(Effectiveness): 모든 명령어는 실행가능해야 한다. 추상 자료형(Abstract data type) 자료형 데이터의 종류 데이터의 집합과 연산의 집합: 연산(operation)에는 함수..

티스토리툴바