NEVAEH

Complexity

• O : Big O, asymptotic upper bound
• Ω : Omega, asymptotic lower bound
• Θ : Theta, order, asymtotic tight bound (O ∩ Ω)

대표적인 복잡도 카테고리

• Θ(lg n)
• Θ(n) : 1차 (linear time algorithm)
• Θ(n lg n)
• Θ(n²) : 2차 (quadratic time algorithm)
• Θ(n³) : 3차 (cubic time algorithm)
• Θ(2ⁿ) : 지수 (exponential time algorithm)
• Θ(n!)

Big O 표기법

• 정의 : 점근적 상한 (Asymptotic Upper Bound)
  
  • 주어진 복잡도 함수 f(n)에 대해서 g(n) ∈ O(f(n))이면 다음을 만족한다 (g(n) : 분석된 결과)
  • g(n) ≤ c x f(n)
  • g(n) ∈ O(f(n)) : g(n)은 f(n)의 큰 오 (big O)
• 어떤 함수 g(n)이 O(n²)에 속한다는 말은
  • 그 함수 (g(n))는 궁극에 가서는 (즉, 어떤 임의의 N값보다 큰 값에 대해서는) 어떤 2차 함수 cn²보다는 작은 값을 가지게 된다는 것을 뜻한다. (그래프 상에서는 아래에 위치)
  • 즉 g(n)은 어떤 2차 함수 cn²보다는 궁극적으로 좋다고 (기울기가 낮다고) 말할 수 있다.
• 어떤 알고리즘의 시간 복잡도가 O(f(n))이라면
  • 입력의 크기 n에 대해서 이 알고리즘의 수행시간은 아무리 늦어도 f(n)은 된다. (f(n)이 상한이다.)
  • 다시 말하면, 이 알고리즘의 수행시간은 f(n)보다 절대로 더 느릴 수는 없다는 말이다.

Ω 표기법

• 정의 : 점근적 하한 (Asymptotic Lower Bound)
  • 주어진 복잡도 함수 f(n)에 대해서 g(n) ∈ Ω(f(n)) 이면 다음을 만족한다 (g(n) : 분석된 결과)
  • g(n) ≥ c x f(n)
  • g(n) ∈ Ω(f(n)) : g(n)은 f(n)의 오메가 (omega)
• 어떤 함수 g(n)이 Ω(n)에 속한다는 말은
  • 그 함수 (g(n))는 궁극에 가서는 (즉, 어떤 임의의 N값보다 큰 값에 대해서는) 어떤 2차 함수 cn²보다는 큰 값을 가지게 된다는 것을 뜻한다. (그래프 상에서는 위에 위치)
  • 즉 g(n)은 어떤 2차 함수 cn²보다는 궁극적으로 나쁘다고 (기울기가 높다고) 말할 수 있다.
• 어떤 알고리즘의 시간 복잡도가 O(f(n))이라면
  • 입력의 크기 n에 대해서 이 알고리즘의 수행시간은 아무리 빨라도 f(n)밖에 되지 않는다. (f(n)이 하한이다.)
  • 다시 말하면, 이 알고리즘의 수행시간은 f(n)보다 절대로 더 빠를 수는 없다는 말이다.

Θ 표기법

• 정의 : Asymptotic Tight Bound
  • Θ(f(n)) = O(f(n)) ∩ Ω(f(n))
  • c x f(n) ≤ g(n) ≤ d x f(n)
  • g(n) ∈ Θ(f(n))은 "g(n)은 f(n)의 차수 (order)"라고 한다.

small o 표기법

• 작은 o는 복잡도 함수끼리의 관계를 나타내기 위한 표기법
• 정의 : 작은 o
  • Big O에 속하는 값 중 최고차항이 더 큰 원소들
  • g(n) ≤ c x f(n)
  • g(n) ∈ o(f(n))은 "g(n)은 f(n)의 작은 오 (o)"라고 한다.
• 큰 O와의 차이점
  • 큰 O : 실수 c > O 중에서 하나만 성립하여도 됨
  • 작은 o : 모든 실수 c > o에 대해서 성립하여야 함
  • g(n) ∈ o(f(n))은 g(n)이 궁극적으로 f(n)보다 훨씬 낫다(좋다)는 의미이다.

차수의 주요 성질

1. g(n) ∈ O(f(n)) iff f(n) ∈ Ω(g(n))
2. g(n) ∈ Θ(f(n)) iff f(n) ∈ Θ(g(n))
3. b > 1이고 a > 1이면, log_an ∈ Θ(log_bn)은 항상 성립. 로그 (logarithm) 복잡도 함수는 모두 같은 카테고리에 속한다. 따라서 통상 Θ(lg n)으로 표시한다.
4. b > a > o이면, aⁿ ∈ o(bⁿ). 지수 (exponential) 복잡도 함수가 모두 같은 카테고리 안에 있는 것은 아니다.
5. a > 0인 모든 a에 대해서 aⁿ ∈ o(n!). n!은 어떤 지수 복잡도 함수보다도 나쁘다.
6. 복잡도 함수를 다음 순으로 나열해보자. Θ(lg n), Θ(n), Θ(n lg n), Θ(n²), Θ(n^j), Θ(n^k), Θ(aⁿ), Θ(bⁿ), Θ(n!) 여기서 k > j > 2이고, b > a> 1이다. 복잡도 함수 g(n)이 f(n)을 포함한 카테고리의 왼쪽에 위치한다고 하면, g(n) ∈ o(f(n))
7. c ≥ 0, d > 0, g(n) ∈ O(f(n)), 그리고 h(n) ∈ Θ(f(n))이면, c x g(n) + d x h(n) ∈ Θ(f(n))

시간복잡도 (Time Complexity) 분석

• 입력 크기의 함수로 일부 기본 연산이 수행되는 횟수를 결정하여 알고리즘의 효율을 분석한다.

표현 척도

• Input size (입력 크기) : 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기, 트리에서 마디와 이음선의 수, 그래프에서는 정점과 간선의 수
• Basic operation (단위 연산) : 비교 (comparison), 지정 (assignment)

분석 방법의 종류

• Every-case time complexity analysis (모든 경우 분석)
  • T(n) : 알고리즘이 n 크기의 인스턴스에 대해 basic operation을 수행하는 횟수 (the number of times the algorithm does the basic operation for an instance of size n)
  • 입력 크기에만 종속
  • 입력 값과는 무관하게 결과 값은 항상 일정
  • ex) Add array members, Exchange sort, Matrix multiplication
• Worst-case time complexity analysis (최악의 경우 분석)
  • W(n) : 알고리즘이 n의 입력 크기에 대해 basic operation을 수행하는 최대 횟수 (the maximum number of times the algorithm will ever do its basic operation for an input size of n)
  • 입력 크기와 입력 값 모두에 종속
  • 단위 연산이 수행되는 횟수가 최대인 경우 선택
  • ex) Sequential search
• Average-case time complexity analysis (평균의 경우 분석)
  • A(n) : 알고리즘이 n의 입력 크기에 대해 basic operation을 수행하는 평균 횟수 (the average number of times the algorithm does the basic operation for an input size of n)
  • 입력 크기와 입력 값 모두에 종속
  • 모든 입력에 대해서 단위 연산이 수행되는 기대치 (평균)
  • 각 입력에 대해서 확률 할당 가능
  • 일반적으로 최악의 경우보다 계산이 복잡
  • ex) Sequential search
• Best-case time complexity analysis (최선의 경우 분석)
  • B(n) : 알고리즘이 n의 입력 크기에 대해 basic operation을 수행하는 최소 횟수 (the minimum number of times the algorithm will ever do its basic operation for an input size of n)
  • 입력 크기와 입력 값 모두에 종속
  • 단위 연산이 수행되는 횟수가 최소인 경우 선택
  • ex) Sequential search

피보나치 수 구하기 알고리즘

• Problem : 피보나치 열의 텀 구하기
• Input : 정수 n
• Output : 피보나치 수의 n 번째 term

# Recursive
def fib(n):
	if n ≤ 1:
    	return n
    else:
    	return fib(n-1) + fib(n-2)

• every-case
• top-down approach
• 재귀함수는 성능이 나쁠 수 있다. 따라서 다음 option까지 생각해보아야 한다.
• 성능이 좋지 않아도, 재귀호출문이 마지막 줄에 있으면 Iteractive 방식으로 코드를 짜지 않아도 된다. (tail recursion)
• T(n) = fib(n)을 계산하기 위하여 fib 함수를 호출하는 횟수. 즉, 재귀 트리 상의 마디 (node)의 개수
• fib(n)의 함수 호출 횟수 계산

              T(n) = fib(n)을 계산하기 위하여 fib 함수를 호출하는 횟수. 즉, 재귀 트리 상의 마디 (node)의 개수

              T(0) = 1

              T(1) = 1

              T(n) = T(n - 1) + T(n - 2) + 1                     for n ≥ 2

                       > 2 * T(n - 2)                                   왜냐하면 T(n - 1) >= T(n - 2)

                       > 2²* T(n - 4)

                       > 2³* T(n - 6)

                       ... ... ...

                       > 2^n-1* T(0)

                       = 2^n-1

• 정리 : 재귀적 알고리즘으로 구성한 재귀 트리의 마디의 수를 T(n)이라고 하면, n ≥ 2인 모든 n에 대하여 T(n) > 2^n/2이다.
• 증명 : (n에 대한 수학적 귀납법으로 증명)

      귀납출발점 : T(2) = T(1) + T(0) + 1 = 3 > 2 = 2^2/2

                       T(3) = T(2) + T(1) + 1 = 5 > 2.83 ≈ 2^3/2

      귀납가정 : 2 ≤ m < n인 모든 m에 대해서 T(m) > 2 이라 가정

      귀납절차 : T(n) > 2n/1 임을 보이면 된다.   (m이 아니라 n일 때도 '참'임을 보임)

                    T(n) = T(n - 1) + T(n - 2) + 1

                          > 2^{(n - 1)/2} + 2^{(n - 2)/2} + 1

                          > 2^{(n - 2)/2} + 2^{(n -2)/2}

                          = 2 x 2^{(n / 2)-1}

                          = 2^n/2

#Iterative
def fib2(n):
	f = []
    
    f.append(0)
    if n > 0:
    	f.append(1)
        for i in range(2, n + 1):
        	f.append(f[i-1] + f[i-2])
    
    return f[n]

• 성능 : T(n) = n + 1

               T(0) = 1

               T(1) = 2

               T(2) = 3

               ... ... ...

               T(n) = n + 1

• bottom-up approach
• 반복 알고리즘은 수행속도가 훨씬 더 빠르다. 중복 계산이 없기 때문이다.

알고리즘

• 문제 해결 기술
• 문제 풀이 절차

알고리즘 중요 특성

• analysis
• efficiency : Time - CPU cycles / Storage - memory
• order : 정확한 결과 값은 아니지만, 카테고리로 분석 결과 제시
• 알고리즘 분석(Analysis) 후 시간/공간 복잡도(Efficiency)를 계산하여 분석 결과(Order)를 도출해낸다.
• cf) complexity의 경우 161이라는 결과를 도출하는 반면, order은 160이상이라는 결과를 출력한다.

알고리즘 문제 표기 방법

• Problem : 답을 도출해내기 위한 추상적인 질문
• List : 특정한 열로 정렬되어 있는 아이템의 집합
• Parameter : 매개변수, 문제에서 특정한 값이 할당되지 않은 변수
• Instance : 매개변수에 지정할 값, 문제의 입력 사례
• Solution : problem의 instance에 대한 답
• Problem 해결법과 Instance 해결법의 차이
  • Problem 해결법 : 형사의 살인범 찾기
  • Instance 해결법 : 형사의 홍길동 살인범 찾기
• 예시 : 검색
  • Problem : n개의 수로 된 리스트 S에 x라는 수가 있는지 알아내시오. x가 S에 있으면 "예", 없으면 "아니오"로 답하시오
  • Parameter : S, n, x
  • Inputs : S = [10, 7, 11, 5, 3, 8], n = 6, x = 5
  • Outputs : "Yes"

Basic Structure

• 정의 부분 : Problem, Input, Output에 관한 설명 기술
• 알고리즘 부분

# python
def procedureName(parameters):
	Body
    
    return ReturnType

// C++
ReturnType procedureName(parameters){
	Body;
}

AOV (activity on vertex) 네트워크 : 정점이 작업을, 간선이 작업 간의 선행 관계를 나타내는 방향그래프 G

• 정점 i로부터 정점 j로의 방향 경로 존재하면 정점 i를 정점 j의 선행자 (predecessor)
• 간선 <i, j>가 존재하면 정점 i를 정점 j의 직속 선행자 (immediate predecessor)
• i가 j의 선행자 → j는 i의 후속자 (successor)
• i가 j의 직속 선행자 → j는 i의 직속 후속자 (immediate successor)
• 위상순서 (topological order) : 임의의 두 정점 i, j에 대해 네트워크에서 i가 j의 선행자이면 선형순서에서도 i가 j 앞에 있는 그래프 정점의 선형 순서

AOE (activity on edge) 네트워크

• 방향 간선 : 프로젝트에서 수행되어야 할 작업
• 정점 : 사건 (event) - 사건은 어떤 작업의 완료를 알림
• 정점에서 나오는 간선이 의미하는 작업은 그 정점에서의 사건이 발생할 때까지 시작될 수 없다.
• 임계경로 (critical path) : 시작정점에서 종료 정점까지의 최장 경로 (longest path)
• 가장 이른 시간 (earliest time) e(i) : 작업 a_i가 시작될 수 있는 가장 이른 시간
• 가장 늦은 시간 (latest time) l(i) : 프로젝트 기간을 지연시키지 않으면서 가장 늦게 작업을 시작할 수 있는 시간
• 임계작업 (critical activity) : e(i) = l(i)인 작업
• 임계경로 분석의 목적 : 임계작업들을 식별해내어 가용 자원을 집중시킴으로써 프로젝트 완료 시간을 단축

신장트리

• 정의 : G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리
  • `깊이-우선 신장트리 (depth-first spanning tree)
  • 너비-우선 신장트리 (breadth-first spanning tree)
• 신장트리는 G의 최소부분 그래프 (minimal subgraph) G'로서 V(G') = V(G)이고 G'는 연결되어 있음.
  • 최소 부분 그래프 : 간선의 수가 가장 적은 부분 그래프
• 신장트리는 n-1개의 간선 가짐
• 통신 네트워크 설계에서 응용
  • 정점이 도시, 간선이 도시 간의 통신 링크
  • 통신 링크의 구축 비용이나 통신 링크의 길이에 가중치를 부여. 총비용이나 총 길이가 최소로 되는 신장 트리를 구함

최소비용 신장트리

• 최소비용 신장트리 (minimum-cost spanning tree) : 최저의 비용을 갖는 신장트리
• Kryskal, Prim, Sollin 알고리즘
• greedy method
  • 최적의 해를 단계별로 구한다
  • 각 단계에서는 몇 개의 판단 기준에 따라 최상의 결정을 내린다
  • 한 번 내려진 결정은 뒤에 번복이 불가능하므로 각각의 결정이 가능한 해를 도출해낼 수 있는지 확인
• 신장트리의 제한 조건
  1. 그래프 내에 있는 간선들만을 사용
  2. 정확하게 n-1개의 간선만을 사용
  3. 사이클을 생성하는 간선을 사용 금지

Kryskal 알고리즘

• 최소비용 신장부분트리를 찾는 알고리즘
• 한번에 하나씩 T에 간선을 추가해가면서 최소비용 신장트리 T를 구축
• T에 포함될 간선을 비용의 크기순으로 선택
• 이미 T에 포함된 간선들과 함께 사이클을 형성하지 않는 간선만을 T에 추가
• G는 연결되어 있고 n > 0개의 정점을 가지므로 정확하게 n-1개의 간선만이 T에 포함됨

Prim 알고리즘

• 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘
• 한 번에 한 간선씩 최소 비용 신장 트리를 구축
• 각 단계에서 선택된 간선의 집합은 트리
• 하나의 정점으로 된 트리 T에서 시작
• 최소 비용 간선 (u, v)를 구해 T ∪ {(u, v)}이 트리가 되면 T에 추가
• T에 n-1개의 간선이 포함될 때까지 간선의 추가 단계를 반복
• 추가된 간선이 사이클을 형성하지 않도록 각 단계에서 간선 (u, v)를 선택할 때 u 또는 v 중 오직 하나만 T에 속한 것을 고른다.

Sollin 알고리즘

• 간선이 하나도 없는 그래프의 모든 정점들로 구성된 숲에서 시작
• 각 단계에서 여러 개의 간선을 선택
• 각 단계에서는 포리스트에 있는 각 트리에 대해 하나의 간선을 선택
• 이 간선은 오직 하나의 정점만 그 트리에 속한 최소 비용 간선
• 선택된 간선은 구축 중인 신장트리에 추가
• 오직 하나의 트리만이 존재 or 더 이상 선택할 간선이 없을 때 종료

깊이 우선 탐색 (Depth-First Search)

• 정의 : 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식
• 인접 리스트의 경우 탐색을 끝내는 시간 O(e+n)
• 인접 행렬의 경우 v에 인접한 모든 정점들을 결정하는데 O(n)의 시간
• n개의 점을 방문해야 하므로 총 시간은 O(n²)

너비 우선 탐색 (Breadth-First Search)

• 정의 : 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용
• 인접 행렬 시간 O(n²)
• 인접 리스트 시간 O(e+n)

연결 요소 (connected component)

• 방문하지 않은 정점 v에 대해 DFS(v) 또는 BFS(v)를 반복 호출로 구함
• 인접리스트로 표현 : 모든 연결요소들 생성 시간은 O(n+e)
• 인접행렬로 표현 : O(n²)

그래프 추상 데이터 타입

• 그래프 G : 2개의 집합 V와 E로 구성
  • V : 공집합이 아닌 정점 (vertex)의 유한 집합
  • E : 간선 (edges)이라고 하는 정점 쌍들의 집합
  • 표기 : G = (V, E)
• 무방향 그래프 (undirected graph)
  • 간선을 나타내는 정점의 쌍에 순서 없음
  • (u, v)와 (v, u)는 동일한 간선
• 방향 그래프 (directed graph)
  • 방향을 가지는 정점의 쌍 <u, v>로 표시 (u는 꼬리(tail), v는 머리(head))
  • <v, u>와 <u, v>는 서로 다른 간선
• 그래프의 제약 사항
  • 자기 간선 (self edge) 또는 자기 루프 (self loop) 없음
  • 동일 간선의 중복 없음
• 완전 그래프 (complete graph) : n개의 정점과 n(n-1) / 2 개의 간선을 가진 그래프
• (u, v)가 E(G)의 한 간선이라면
  • u와 v는 인접 (adjacent)
  • 간선 (u, v)는 정점 u와 v에 부속 (incident)
• 그래프 G의 부분그래프 (subgraph)
  • V(G') ⊆ V(G) 이고 E(G') ⊆ E(G)인 그래프 G'
• 정점 u로부터 정점 v까지의 경로 (path)
  • 그래프 G에서 (u, i₁), (i₁, i₂), ... , (i_k, v)를 E(G)에 속한 간선들이라 할 때, u로부터 v까지의 경로는 u, i₁, i₂, ... , i_k, v
• 경로의 길이 (length)
  • 경로상에 있는 간선의 수
  • (0, 1), (1, 3), (3, 2) == 0, 1, 3, 2
  • G₁에서 경로 0, 1, 3, 2와 경로 0, 1, 3, 1은 길이가 3인 경로
• 단순 경로 (simple path)
  • 경로상에서 처음과 마지막을 제외한 모든 정점들이 서로 다름
  • G₁에서 0, 1, 3, 2는 단순 경로, 0, 1, 3, 1은 단순 경로 아님
• 단순 방향 경로 (simple directed path)
  • G₃에서 0, 1, 2는 단순 방향 경로
  • G₃에서 0, 1, 2, 1는 경로가 아님
• 사이클 (cycle)
  • 처음과 마지막 정점이 같은 단순 경로
  • G₁에서 0, 1, 2, 0는 사이클
  • G₃에서 0, 1, 0는 방향 사이클
• 연결 요소 (connected component) : 최대 연결 부분 그래프 (maximal connected subgraph)
• 강력 연결 (strongly connected) : 방향그래프에서 V(G)에 속한 서로 다른 두 정점 u, v의 모든 쌍에 대해서, u에서 v로, 또한 v에서 u로의 방향 경로(directed path)가 존재
• 강력 연결 요소 (strongly connected component) : 강하게 연결된 최대 부분 그래프
• 차수 (degree) : 정점에 부속한 간선들의 수
• 진입 차수 (in-degree) : 임의의 정점 v가 머리가 되는 간선들의 수
• 진출 차수 (out-degree) : v가 꼬리가 되는 간선들의 수
• 간선의 수 : e = ($\sum_{i=0}^{n-1}\left(d_i \right)$) /2  (n개의 정점과 e개의 간선을 가진 그래프
• 다이그래프 (digraph) : 방향 그래프
• 그래프 : 무방향 그래프

그래프 표현법

• 인접행렬 (Adjacency Matrix)
  • G = (V, E)는 정점의 수가 n(n ≥ 1)인 그래프
  • 인정행렬 : nxn의 2차원 배열
  • 간선 (v_i, v_j) ∈ E(G) ⇒ a[i][j] = 1
  • 간선 (v_i, v_j) ∉ E(G) ⇒ a[i][j] = 0
  • 필요 공간 : n² 비트
  • 무방향 그래프 : 어떤 정점 i의 차수는 그 행의 합 : ($\sum_{i=0}^{n-1}a[i][j]$)
  • 방향 그래프 : 행의 합은 진출차수, 열의 합은 진입차수
  • 인접행렬의 수행 시간 : 최소한 O(n²)
  • 희소 그래프 (sparse graph) : O(e + n)
• 인접리스트 (Adjacency Lists)
  • 인정행렬의 n행들을 n개의 연결리스트로 표현
  • data와 link 필드
  • n개의 정점, e개의 간선의 무방향 그래프 : 크기가 n인 배열, 2e개의 체인 노드가 필요
  • 방향 그래프 : e개의 체인 노드

가중치 간선 (Weighted Edges)

• 그래프의 간선에 가중치 (weights) 부여
• 인접행렬 : 행렬 엔트리에 a[i][j]의 가중치 정보 저장
• 인접리스트 : 노드 구조에 weight 필드를 추가
• 네트워크 (network) : 가중치 간선을 가진 그래프