Jeonghun (James) Lee: 10월 2016

10/27/2016

Graph

1. Graph (그래프)의 기본이론

그래프는 기본적으로 두가지 요소로 표시되며, V(vertices)와 E(edge)로 이루어진다.

Vertices는 정점을 말하며 Edge는 이어주는 다리라고 생각하면 되겠다.

그래프에서는 정점(Vertices)들은 객체나 다른 요소들로 의미 부여가 가능하며, 연결(Edge)는 정점과의 관계 혹은 연결이라고 생각하여
이를 추상화하여 생각한 다음 만들어 이를 생성하면 그것이 바로 그래프가 되는 것이다.

그래프의 구조

상위에서 설명했듯이 기본은 정점과 연결이지만, 연결에는 방향성이라는 것이 존재하기 마련이다.
이를 두고 그래프에서도 방향성(directed) 을 가지고 있느냐, 아니면 무방향성(undricected) 인가에 따라, 그래프의 종류가 나뉘어지며,

방향성(directed) 그래프는 때로는 arch라고도 말한다.

Graph Wiki
https://en.wikipedia.org/wiki/Directed_graph
https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#Undirected_graph

1.1 기본 그래프 표시

기본개념을 알았으니, 그래프를 어떻게 수식으로 표현을 하는지를 알아봐야겠다.
아래와 같이 기본 그래프들은 아래와 같이 표시한다.

G = (V,E)

G의 두개(V,E) 의 수식이 정점을 표현을 하기때문에 상위 G는 연결(Edge)를 표현을 해준다고 생각하면 되겠다.
예를 들면, 방향성 그래프에서 한 Edge가 정점 u에서 정점 v로 간다면 이를 (u,v)로 표시

1.2 그래프 표시 적용 예

아래의 그래프는 무방향성(undirected) 그래프로 이를 표현하기 위해서는 무방향성 그래프의 특징을 알아야한다.
무뱡향 그래프는 (u,v)와 (v,u) 가 동일하며, 이 중복된 부분들은 생략을 한다.

아래의 그림과 같이 정점(V)은 총 6개로 구성된다.

V={1,2,3,4,5,6}

그리고 아래와 같이 현재 무방향성이기 때문에 G를 표현을 하면 아래와 같이 연결된 노드는 7개로 구성이 된다.

E={ (1,5) , (1,2) (2,5) , (2,3) , (3,4) , (4,5) , (4,6) }

https://en.wikipedia.org/wiki/Graph_theory

Graph 이론
https://en.wikipedia.org/wiki/Graph_theory
https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)

1.3 Graph의 기본 용어 정리

이제 그래프의 기본 표현방식과 관련된 부분을 알아봤으니 관련용어들을 알아보자.

무방향성(undirected) 그래프의 용어

무뱡향성 그래프에서 생각할 것은 정점과 연결이 되었는지 혹은 연결된 갯수는 몇개인지가 중요하다

차수(degree) : Vertex에서 연결되는 Edge의 수, 쉽게생각하면 한 정점에서 연결된 노드수
인접(adjacent or adjacency): 두개의 Vertex가 사이에 Edge 있다면 이를 Adjacent라고 한다, 즉 연결된 노드가 있다면 이를 인접

방향성(directed) 그래프의 용어

방향성 그래프의 경우는 연결이 되어 있다고 하더라도 방향을 생각해야하기에 정점 기준으로

들어오는 노드 혹은 나가는 노드를 생각해야한다.

정점(vertex)의 입력차수(in-degree): Vertex에 들어오는 Edge의 갯수
정점(vertex)의 출력차수(out-degree): Vertex에 나가는 Edge의 갯수

아래용어참조

https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_%EC%9D%B4%EB%A1%A0_%EC%9A%A9%EC%96%B4%EC%82%AC%EC%A0%84

1.4 Graph의 연결성과 순환성 (connectivity)

방향성 그래프와 무방향성 그래프는 연결성의 성질이 다르며, 이부분에 대해 좀 정확히 구분하기 위해서

아래와 같이 조건과 용어를 구분하여 설명하였다.
https://en.wikipedia.org/wiki/Connectivity_(graph_theory)
https://en.wikipedia.org/wiki/Connected_component_(graph_theory)

개인적으로 볼때, 그래프에서 잊지 말아야할 부분은 그래프의 순환성이며,

연결된 그래프를 구성하여 이를 동작할 때 루프에 빠질 수 있기 때문이다.
컴포넌트 개념은 정점의연결이며 이를 확장 및 또 다른 Graph의 연결하고,

상위 순환성 문제에서 Loop를 빠지는 것을 방지하기 위해서,
방문한 장소를 기록하는 방법이 있다.

DAG(directed acyclic graph) : 방향성 비순환 그래프 ( Loop가 존재 하지 않는 Graph)
acyclic : 비순환성 의미한다

https://en.wikipedia.org/wiki/Directed_acyclic_graph (DAG , directed)
https://en.wikipedia.org/wiki/Tree_(graph_theory)#Forest (Forest, undirected)

1.조건-A

모든점(Vertex)들이 어떤 경로 즉, Edge를 걸쳐 서로 도달 할 수 있고 연결되어있다.

무방향성 그래프

조건-A의 용어: 연결(connected)

방향성 그래프

조건-A의 용어: 강한연결(strongly connected)

2. 조건-B

component의 정의가 다른 것 같다.

무방향성(undirected) 그래프

연결(connected)이 되어있지 않더라도, 즉 조건-A를 만족하지 않더라도 어떤 특정 연결된 컴포넌트 (connected component)를 포함할 수 있다.

-용어: 연결된 객체 (connected component)

아래는 3개의 연결되지 않은 component를 보여준다.

https://en.wikipedia.org/wiki/Connected_component_(graph_theory)

방향성 (directed) 그래프

아래에서 일부분 만이 강하게 연결되었을때, 강하게 연결된 컴포넌트(strongly connected component)라고 한다.

-용어: 강하게 연결된 객체(strongly connected component)

아래의 예를 들어보자. 3개의 strongly connected component 존재한다

Vertex : {a, b, e}
Vertex: {f, g}
Vertex: {c, d, h}

https://en.wikipedia.org/wiki/Strongly_connected_component

위 그래프를 간단히 분석해보면,

두 component 사이에 (b,c) dashed edge가 연결이되어 component가 연결이 된다.
a -> f 까지 연결이 가능하다 하지만, a->f 걸쳐 -e로 가지 못한다.
(f,g) 와 (c,d), (d,h)는 순환성을 가지고 기본적인 두 정점사이의 순환성을 가지고 있고,
a->b->e도 역시 순환성을 가지고 있다.

참고: C로 구현한 알고리즘 책

2. Graph 구현 방법

2.1 Adjacency Matrix ( Array 구현)

배열이 1부터 시작

Graph를 2차원 배열로도 표현이 가능하며 이를 Matrix로 표현이 가능하다.
2차원 배열로 표현을 한다면, 우선 중요한 것은 정점의 갯수로 NxN 배열을 구성하는 것이다.

그리고 상위 그림과 같이 정점의 입/출력차수를 2차원배열로 표현을 하는 것이다.
2차원배열로 구성할 경우에는 기본적으로 방향성그래프로 표현이 가능하기에, 무뱡향성 그래프도 표현이 가능하다.

상위 2차원 배열을 간단히 분석하면, X축과 Y축는 Vertex를 의미하고 배열 안의 값이 0,1,2 에따라 Edge의 상태가 표시된다.

배열의 값 0: 미 연결
배열의 값 1: 단방향 연결 됨
배열의 값 2: 대각선만 이 값을 소유가능 (자신 Loop) (서로의 edge 더하여 2표시)

상위 그림을 보면 무뱡향성 그래프이기때문에, 대각선을 기준으로 대칭을 이루고 있다.

Matrix 대각선

Matrix 대각선(상위왼쪽->하단오른쪽) 좌표 상위를 그림을 보면 위와 같다. (v,u) 와 (u,v)가 동일하며, 값은 0과 2로 표현

좌표 (1,1)=2 // 동일한 정점 두개가 연결이 되었기 때문에 이를 2로 정의
좌표 (2,2)=0,
좌표 (3,3)=0
좌표 (4,4)=0
좌표 (5,5)=0
좌표 (6,6)=0

상위 그래프가 무향성 그래프이며 Matrix 대각선(상위왼쪽->하단오른쪽) 기준으로 대칭을 이루고 있어서 대각선 기준으로 한쪽부분 만 보면된다.

좌표 (1,2) (2,1) = 1
좌표 (1,5) (5,1) = 1
좌표 (2,3) (3,2) = 1
....

방향성 (directed) 그래프

위 Matrix는 기본적으로 단방향성을 가지고 있어서 방향성(direct)을 표현이 가능하기 때문에 아래와 대각선 기준으로 위/아래를 입/출력으로 생각을 하면 쉽게 이해가 간다.

각 2차원 배열은의 값들은 Vertex 의미한다 (배열 1부터시작)

matrx[1][2] (1,2) = 1 이는 1 -> 2 연결
matrx[2]1] (2,3) = 1 이는 2 -> 3 연결

X,Y축의 갯수는 Vertex의 출력차수이며, 동일하다
X축은 시작점(Vertex)과 Y축은 종료점(Edge)

위에서 보았듯이 X축이 시작점이기 때문에 구현을 할때에도, column 기준으로 검색을 해야한다.

https://en.wikipedia.org/wiki/Adjacency_matrix
http://mathworld.wolfram.com/AdjacencyMatrix.html

2.2 Linked List 로 표현

위는 Matrix로 표현하기에 한정적으로 표현이 가능하지만, Set or Linked List로 표현을 하게되면 동적으로 확장이 마음대로 가능하다.
Set도 내부적으로 보면 Linked list로 구현하기때문에, Linked List로 표현했다.

확장개념은 위에서 본 컴포넌트 개념을 보면되겠다.

간단한 표현방법은 개별 Vertex는 Linked List를 가지고 있으며, 각 Edge 값들을 이곳에 보관하는 방법이다.

이곳에서 다루기에는 좀 소스가 커진다.

3. Graph의 탐색(Search) 방법

일반적으로 Graph에서 Search 하는 방법은 너비 우선(Breadth-first) or 깊이 우선(Depth-first)

DFS와 BFS는 Graph에만 한정되는 것이 아니라, Binary Tree에도 적용이 되며 다중으로 연결된 Graph 에도 적용이 된다.

3.1 Depth First Search

Adjacency Matrix를 이용하여, DFS 를 구현

DFS ( Depth First Search)는 일반적으로 Queue가 필요가 없고,
현재 근처 노드의 연결상태를 확인한 다음 근처 노드로 진행을 하고,
지나간 기록하면서 이를 찾아가는 방식이다.

아래의 예제는 방향성이 없는 DFS (Depth First Search)의 예제

http://cyberlingo.blogspot.kr/2015/03/depth-first-search-adjacency-matrix.html
http://www.thecrazyprogrammer.com/2014/03/depth-first-search-dfs-traversal-of-a-graph.html

https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm

DFS (Adjacency Matrix가 아닌 경우를 이용하여 사용)

http://blog.eairship.kr/268

3.2 Breadth First Search

Adjacency Matrix를 이용하여, BFS 를 구현

BFS( Breadth First Search)는 현재 Node인 Vertex를 Queue에 삽입하고,
Queue에 있는 Node에 연결된 모든 Edge 찾아가는 방식이지만,
구지 Edge가 아니여도 좋다.

https://en.wikipedia.org/wiki/Breadth-first_search
  https://namu.wiki/w/BFS
  https://www.tutorialspoint.com/data_structures_algorithms/breadth_first_traversal.htm

BFS ( Adjacency Matrix가 아닌 경우를 이용하여 사용 )

  http://blog.eairship.kr/269

C언어 Symbol (수정중)

1. C 언어의 Symblol

1.1 weak

C언어에서 weak라는 symbol이 있는데 주로, function 앞에 붙혀서 사용을 한다.
이는 C++의 virtual sysmbol의 개념과 비슷한데,
weak function을 사용하면 함수의 override를 같은 이름의 중복(override) 허용을 한다.

사용법은 만약 첫번째 sfunc1을 사용하고 싶다면, 두번째 함수를 정의를 하지 않고
이를 호출하면 첫번째 func1이 호출이 된다.

하지만, 두번째 sfunc1() 사용하고 싶다면 이를 정의를 하여 중복(override) 허용이 되기에
이를 호출하면, 두번째 sfunc1() 호출이 된다.

weak int sfunc1()
{

}

int sfunc1()
{

}

이를 일반적인 사용법을 적용을 해보면 아래와 같다.

일반 처음 배포판은 weak로 작성을 하여 배포를 하여, release를 하게되면,
User들은 기본 배포판의 weak function 들을 사용해도 되지만, 이를 재정의해서 자신만의 함수로 사용을 해도 된다.

상위 개념은 객체지향의 virtual symbol과 유사하다.

ELF에서는 이를 dynamic linking 이라고 하며, 일반적으로 dynamic binding 이라고 부른다
왜냐하면, 일반적인 함수는 static binding 즉, Complie 시간에 모든것이 결정이 되지만,
위 함수는 호출 할 함수가 아직 결정이 되지 않았다.

shared library를 사용하게되면, 이는 linker는 dynamic linking 를 통해 호출할 함수를 찾아 호출하는 것이다.

http://occamsrazr.net/tt/8

Marcro (__LINE__, __FILE__, #expr, __func_)
http://yesarang.tistory.com/74

https://en.wikipedia.org/wiki/Weak_symbol
https://docs.oracle.com/cd/E19683-01/816-1386/chapter2-11/index.html

10/26/2016

C++ 과 Java 정리 (수정 중)

다시 C++ 과 Java 정리

다형성 (Polymorphism)

상속(Inheritance)

다중상속(Multiple inheritance)
Java x
C++ o

overriding

overloading

private
protected
public
virtual
  https://ko.wikipedia.org/wiki/%EA%B0%80%EC%83%81_%ED%95%A8%EC%88%98
  http://marobiana.tistory.com/84
  http://stackoverflow.com/questions/4547453/can-you-write-virtual-functions-methods-in-java

http://tip.daum.net/question/58306551

http://blog.eairship.kr/175

http://pacs.tistory.com/entry/C-%EC%83%81%EC%86%8D-%EB%91%90%EB%B2%88%EC%A7%B8-%EC%84%B8%EA%B0%80%EC%A7%80-%ED%98%95%ED%83%9C%EC%9D%98-%EC%83%81%EC%86%8D-private-protected-public

2. Java 관련 문법

  http://misoleaf.blogspot.kr/2013/01/java.html

Java의 기본개념 및 문법의 이해

JDK (Java Development Kit) 와 JRE(Java Runtime Environemnt)의 차이 및 구조
Java 8 SE(Standard Edition) API의 범위
Java ME(Micro Edition), Java EE(Enterprise Edition), JAVA Card
기본문법
http://nyebo.net/2016/01/just-java-summary/

Java의 Class의 기본구조 및 inner class 사용법

Java의 Class의 기본구조
http://jsnote.tistory.com/21

  https://www.tutorialspoint.com/java/java_innerclasses.htm

Java의 inner class 사용법
  http://tworab.tistory.com/49

Java의 inner class를 이용한 캡슐화 진행
  http://gangzzang.tistory.com/entry/Java-%EB%82%B4%EB%B6%80%ED%81%B4%EB%9E%98%EC%8A%A4inner-class

  https://www.careercup.com/question?id=5757216146587648

10/25/2016

Hash Table

1. Hash Table 기본개념

Hash Table의 기본 개념은 Key가 존재하며, hash function 이 존재하고, buckets이 존재한다.

- 기본개념과 용어

Keys

key는 유일한 존재이며, 중복이 되어서는 안된다. 중복이 될 경우 1:1 Mapping 문제가 발생.

hash function :

key 값을 입력을 받아 가능한 매번 균등한 일정 값 이 나와야 한다.
key 값을 입력을 받으면 결과 값은 매번 동일해야 한다.

buckets

key와 bucket을 1:1 mapping이 되도록 하기 위해서 만들어 놓은 저장장소
hash function은 완전한 1:1 mapping 제공하지 않는다 (충돌문제 발생)

key는 아래와 같이 data가 될 수있으며, hash function 을 통하여 bucket 에 균등하게 mapping 되도록 노력한다.

쉽게 설명하면, 어떤 이름을 가진 table을 빠르게 검색하고 싶은 경우를 생각을 해보자.
이 이름을 Key로 사용하고 Hash Function의 이 이름을 분석하여, bucket list 중 하나에 이를 1:1 mapping 하도록 하면 빠른 검색이 가능하다.

이렇게 하면, 빠른 검색이 가능하지만, 여기서 기본적인 문제점이 있다.
Hash 함수의 균일성 유지 문제이다. 그래서 여분의 Bucket 있음에도 불구하고
Key값의 충돌이 발생이 한다.

가능한 Hash 함수가 균일성을 유지하고 Key값과 Bucket을 1:1 Mapping 유지하도록 했다면,

균일성 문제로 충돌을 해결하는 방안으로 찾아보자.
이에 따라 Hash Table의 종류가 변경이 된다.

https://en.wikipedia.org/wiki/Hash_table

2. Hash Table의 종류

위의 설명을 보면, hash function이 중요하다는 것을 알 수 있으며, 충돌문제가 발생할 수 있다는 것을 알수 있다.
key 값을 넣어 hash table을 가능하면, 균등하게 매번 동일하게 mapping하여 빠른 검색을 해야한다.

하지만, Key 값을 Hashing 하여 bucket 값이 충돌이 될 경우
이를 해결하는 방법은 크게 두가지로 나누어지며, 아래와 같이 볼수 있다.

2.1 Chained Hash Table

사용할 Bucket 숫자 와 함께 Linked List를 만들어, 데이타를 추가 할 경우 기존에 이미 해당 Bucket에 존재 할 경우,
이는 충돌이 되어, 아래와 같이 같은 Bucket에 linked list를 만들어 관리한다.

이는 Bucket의 충돌을 허용하여, 이를 Linked List로 별도로 관리를 한다.

2.2 Open-Addressed Hash Table

위와 같이 충돌이 날 경우, Open-Addressing 일 경우, 다른 방안으로 이를 해결을 한다.
충돌을 해결법은 다시 빈 Hash Table을 찾을 때까지 검색하여, 이를 그 곳에 넣는것이다.

이때 Hash 하는 방법은 아래와 같은데, 아래 예제는 Hash 함수를 두개 사용한 Double hasing 이다.

A. 충돌문제방법(Collision resolution)

아래와 같이 충돌이 발생할 경우, Open-Addressed Hash Table은 이 충돌을 피하기 위해,
다양한 방식을 제공을 한다.

1. Linear Probe 방식

충돌이 발생할 경우, 충돌 지점부터 순서대로 빈칸 bucket을 찾아 그곳에 Data를 삽입.

아래사이트 참고
  https://en.wikipedia.org/wiki/Linear_probing

2. Quadratic Probe 방식

충돌이 발생할 경우, Hash 함수에 패턴을 가지고 변형을 가해 빈칸을 찾아 그곳에 삽입.
아래 사이트 참고

  https://en.wikipedia.org/wiki/Quadratic_probing

3. Double Hash 방식

충돌이 발생할 경우, 기본적으로 Hash함수를 두개를 사용하고 하나는 기본 Hash함수와
별도의 하나는 값의 변경에의해 변경될 Hash 함수로
매번 다른 값을 균일하게 나오도록 하여, 빈칸을 찾아 그곳에 삽입

한마디로, 빈 Bucket 을 찾을 때까지 2개의 hash 함수로 찾는 것이다.

https://en.wikipedia.org/wiki/Double_hashing

4. 기타 방식들

아래 사이트가면 자세히 설명
  https://en.wikipedia.org/wiki/Hash_table

위 방식들은 빈 Bucket을 찾는 방식은 서로 다르나, 기본적인 취지는 동일하다.
충돌이 일어날 경우, 다시 빈 Bucket을 찾는 것이다.

B. 충돌문제방법 예

Double Hash 방식

아래의 예제는 Double Hash 기준으로 작성된 예제이다.
소스로만 보면, 최악의 경우 최대 Bucket 수 까지 검색해야 한다.

하지만, 핵심은 Hash 함수가 동일한 Key 입력을 받을 경우 동일한 Bucket 값으로 Mapping이 되기에
이 문제는 최악으로 가지는 않을 것이다.

/*
      htbl->positions : 전체 사용할 bucket 수 
      htbl->h1  , htbl->2 :  2개의 hash 함수 
      position        : bucket 

      refer to :  Mastering Algorithms with C
*/

for(i=0; i < htbl->position;i++)  // 자료를 찾을 때까지 , 전체 bucket 수 까지 반복하면서 찾는다.
{
   position = (htbl->h1(*data) + (i * htbl->h2(*data))) % htbl->positions;

   if(htbl->table[position] == NULL){ //자료를 없을 경우 
      
     return -1;
   
   }else if(htbl->match(htbl->table[position],*data)){ // 자료를 찾을 경우, 

      *data = htble->table[position];

   }

}

위의 Double Hashing 과 함께 예제를 통해 간단히 알아보자.
전체 Bucket 수가 10개 있을 경우, 초기 값이 00일 경우

h(k,i)

k : 삽입되는 key data
i : 반복되는 횟수

0 1 2 3 4 5 6 7 8 9
1: [00] [00] [00] [00] [00] [00] [00] [00] [00] [00] : i=0 일 때 k = 23, 45, 55, 77 삽입
2: [00] [23] [00] [45] [00] [55] [44] [77] [00] [00] : i=0,1 로 k = 44 (1번 충돌)
3: [00] [23] [66] [45] [00] [55] [44] [77] [11] [00] : i=0,1,2,3,4 로 k = 66, 11 (4번 충돌)

참조 : C로 구현한 알고리즘

Linear Probe 방식

아래의 그림은 기본적으로 Linear Probe 방식이을 나타낸다.

C. 참고사항

Open addressed Hash Table 2번 이상 충돌된 Bucket을 삭제할 경우,
1번째 충돌이 된 Bucket을 삭제를 하면 이 상태가 모호해지므로, 이부분의 상태를 구분을 해주는데,
만약 이 부분도 무시하고 싶다면, loop에서 continue로 넘어가면되지만, 좀 성능저하가
발생된다.
그래서, remove시 이때 unique한 다른 값을 넣어, 초기 값과 remove 상태를 구분지어 주는 것이다.

예를 들면, Bucket에 Pointer 주소를 넣어준다. 위와 같이 구현을 한다.

참조 : C로 구현한 알고리즘 ( vacated 사용부분)
http://bcho.tistory.com/1072

3. Hash Table의 비교 및 성능분석

위 상위 두개 Hash Table을 성능을 찾기를 했을 경우, 평균 Cache Miss가 일어나는 경우를
나타내는 그림이며, 상위 두개의 Hash Table을 비교를 해보자.

잘 알다시피 Cache Miss가 일어나며, CPU는 Cache에 Data가 없기에, RAM에서 다시 가져와야한다.
아래는 Cache HIT가 아니라 Cache Miss임을 알아두자, 높으면 높을 수록 안좋다.

X의 좌표의 Load Factor는 아래와 같이 설명된다.

Load factor = n/k

n: the number of entries ( 현재 사용하고 있는 entry)
k: the number of buckets ( 총 bucket 수 )

한마디로 Load factor는 Bucket의 사용률을 퍼센트로 표시한 것이다.
그래서 Open Addressed 경우 사용률을 80%가 넘어가면 안되겠다.

상위 그림을 보면, 내 개인적인 생각으로는 Load factor 기준으로 비교해 보면

Chaining은 평균 Cache Miss 2~ 3정도로 꾸준히 유지하는이유는 처음 나도 궁금했으나, 생각을 해보니
이유를 알것 같다. Chaining은 Linked List 가 필요하며, 이때 매번 새로운 Access 문제가 발생한다.
충돌을 하든 안하든 새로운 Linked List Access 요구가 필요하고, 충돌이 될 경우는
Linked List의 에서
다음 Element를 검색을 한번 더 해야하니 2~3정도로 유지하는 것이 맞는것 같다.

Open-Addressing는 Data 를 Table에 직접 Mapping하여 상위문제는 없어 빠르다.
하지만, Load Factor가 증가하면 할 수록 확률적으로 충돌횟수는 증가할 것이고,
이는 곳 Cache Miss 횟수가 늘어날 수 밖에 없는 구조이다.
현재 위 그림은 Open-Addressing의 (Linear Probing) 경우 이지만, 다른 모델도 거의 비슷할 것으로 생각한다.

상위기본 문서는 아래의 wiki 참조하여 작성했으며, 더 자세한 내용 아래의 Wiki 참조.
https://en.wikipedia.org/wiki/Hash_table
https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94

4. Hash Table 예제

4.1 Open-addressed Hash Table

아래의 예제는 open-addressed hash table이며, vacated 로 remove시
이를 구분하도록하였지만, 2번 이상 remove를 하면 이것도 사실 필요가 없다.
처음 코딩할때 부터 여러번 remove를 할 것이면, 구지 만들필요가 없는 개념이다.

10/24/2016

기본정렬 (Sorting Algorithm)

1. (Sorting Algorithm) 정렬 알고리즘 기본내용

일반적으로 정렬은 가지고 있는 Data 를 Ascending 오름차 순으로 or
Descending 내림차순으로 가지고 있는 data list를 순서를 변경하는 것이다.

이를 한정적으로 숫자에 그리고, 적용범위를 위와 같이 한정짓으면 위와 같이 되겠지만,
적용범위를 넓히면 다양하게 Sorting을 할 수도 있겠다.

일단 목적이 기본적으로 Sorting Algorithm 학습이기에 알아둬야 할 기본 용어 부터 알아보자.

ascending sort or ascending order (오름차순 정렬 ): 1,2,3,4
descending sort or descending order (내림차순 정렬): 4,3,2,1

2. 정렬 (Sorting Algorithm ) 비교 및 pseudo code

일반적으로 많이 사용되는 정렬 알고리즘이며 pseudo code 이들을 간단히 살펴보자.

bubble sort: https://www.toptal.com/developers/sorting-algorithms/bubble-sort
insertion sort: https://www.toptal.com/developers/sorting-algorithms/insertion-sort
selection sort: https://www.toptal.com/developers/sorting-algorithms/selection-sort
shell sort: https://www.toptal.com/developers/sorting-algorithms/shell-sort
quick sort: https://www.toptal.com/developers/sorting-algorithms/quick-sort
quick3 sort: https://www.toptal.com/developers/sorting-algorithms/quick-sort-3-way
merge sort: https://www.toptal.com/developers/sorting-algorithms/merge-sort
heap sort : https://www.toptal.com/developers/sorting-algorithms/heap-sort

이외에도 다른 많은 Sorting Algorithm 이 존재하며 이를 다 알기가 힘들어서 여기서 다루지는 않겠다.

상위 정렬들의 Working Time 비교분석

https://www.toptal.com/developers/sorting-algorithms/

3. 정렬 알고리즘 기본학습

기본적인 Sort만 다루겠지만, Heap sort는 priority Queue 함께 다루겠다.

3.1 기본적으올 알아둬야 할 정렬 알고리즘

Bubble Sort
Insertion Sort

https://en.wikipedia.org/wiki/Insertion_sort
https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

버블정렬은 알 것이지만, Insertion Sort는 한번 살펴보자.

https://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm
https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm

3.2 대표적으로 좋은 성능 내주는 정렬 알고리즘

Quick Sort
Merge Sort

위 두 정렬은 divide and conquer algorithm 이며, sorting 하는 방법도 유사하다.
divide하는 방식은 같지만, conquer의 역할이 다를 뿐이다.

Quick는 divide 다 한 후, 교환하는 방식으로 간다고 정렬하지만,
Merge는 divide 다 한 후, 별도의 Memory 공간에 이 정렬되는 과정을 넣어 이것을 정렬한다.

이 둘의 차이는 Memory의 사용량의 차이

https://www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm
https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_algorithm.htm

A. Quick Sort

data array 중 한 data를 선택하여 이를 Pivot하고 기준으로 정한다.
Partitioning은 이는 array를 다시 순서를 맞추는 작업이다.
Partitioning에서 얻은 큰 값을 기준으로 sub-array 작업을 반복적으로 한다.

Partitioning
왼쪽에서 pivot 위치까지 pivot 보다 작은 데이타 위치를 찾는다.
오른쪽에서 pivot 위치까지 pivot 보다 큰 데이타 위치를 찾는다.

https://en.wikipedia.org/wiki/Quicksort
https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC
http://www.cquestions.com/2008/01/c-program-for-quick-sort.html

아래의 소스는 Quick sort C로 구현을 해본것이다.

B. Merge sort

https://en.wikipedia.org/wiki/Merge_sort
https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

Merge sort examples

  https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_program_in_c.htm
  http://yujuwon.tistory.com/entry/%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%ACMerge-Sort

  http://nukestorm.tistory.com/54

10/23/2016

기본자료 구조 (Linked List 와 Queue, Stack )

아래는 제가 Single Linked list 와 Array로 간단하게 Queue와 Stack을
Programming 하고, Test를 해봤습니다.
버그가 있다면 말씀해주시면 감사하겠습니다.

기본적으로, Queue 는 FIFO 구조 이며, Stack는 LIFO 구조 입니다.
Queue와 Stack의 동일한 점은 Data를 넣는 지점은 TAIL 이지만,
다른 점은 데이타를 꺼내는 지점 HEAD or TAIL 따라 queue 와 stack으로 나누어지게 됩니다.

1. Single Linked List ( Queue 와 Stack )

2. Array Queue and Stack

10/22/2016

Tree (data structure)

1. Tree의 일반적인개념

Tree 구성

Tree의 기본구성은 Parent node에 child node로 연결된 추상적인 자료구조로
Tree의 element는 Node이며 Tree의 선을 branch라고 말한다.
그리고, 마지막 Node , 즉 Child node가 없는 leaf node , end-node 라고 부른다.

좀 더 자세히 설명을 하게되면, Graph와 동일하게 표시도 가능하겠지만,
Tree는 방향성과 계층의 속성을 가지고 있기에 이를 분리하여 표시한다.

Tree의 종류

Tree는 종류 다중 Tree와 2진 Tree로 구분 할 수 있겠다.
일반적으로 2진 트리, Binary Tree를 많이 사용한다.

Tree의 재귀(Recursion)

Tree에서 Recursion (재귀)는 자주 사용이되며, 이는 탐색 (Traversal) 에 용이하다.

https://en.wikipedia.org/wiki/Tree_(data_structure)
https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

1.1 Trie 트라이, MultiTree (다중 트리) 소개

쉽게 생각하면 탐색기에서 사용하고 있는 디렉토리가 다중 트리이며,
데이타베이스에서 주로 사용이 된다.
이 곳에서는 다루지는 않겠다.

트라이 (Trie)
  https://en.wikipedia.org/wiki/Trie

https://en.wikipedia.org/wiki/Multitree

B Tree or B+ Tree
  https://en.wikipedia.org/wiki/B%2B_tree
  https://ko.wikipedia.org/wiki/B_%ED%8A%B8%EB%A6%AC
  https://ko.wikipedia.org/wiki/B%2B_%ED%8A%B8%EB%A6%AC

1.2 Binary Tree 소개

Child Node를 2개로 한정지어 Tree를 구성하도록 하는 트리를 말하며, 일반적으로
많이 사용이 되어진다.

Node 기준 left child 와 right child 존재하며, 상위 처음 Node 를 Root라고 말한다.

구현방법은 Tree 구조체를 이용하는 방법도 있겠지만, Array로도 구현이 가능하다.

2. Binary Tree 구현방법

2.1 Tree 구조체 사용하여 동적구현

장점: 유지보수 및 삭제의 용이성 , 동적으로 추가 ,삭제가 쉽다.
단점: 구현이 새로운 구조체와 여러 함수를 필요하다보니 좀 복잡하다.

struct Node {
int data ; // void * data;
.... // 다른 Data
struct Node *left;
struct Node *right;
}

struct Tree {
int size;
struct Node *root; // 전체 root
struct Node *prenode; //searching 할때, 현재 node의 root
.... // 이밖에 필요한 정보 및 함수 포인터도 삽입가능
}

2.2 Data Array 정적 구현

이 부분 추후 Heap sort 와 우선 순위 Queue에서 다시 사용하겠다.

장점: Data Array 가장 쉽게 구현이 가능하다.
단점: Node의 삭제가 어렵고, Array Size로 인하여 이미 지속적인 유지보수가 힘들다.

0은 Root 이며, Level 0
1,2 Root의 left , right Level 1
3,4 1의 left, right Level 2
5,6 2의 left, right Level 2

그래서 총 3층의 2진트리로 구성이 가능하며, 이는 구성이 Breath-First Search 개념 유사하다.
다만,

아래 그림은 Array 0부터 시작을 했고, Level도 0부터 시작을 했다

Node 의 수가 Data 존재여부가 아닌 계층(Level)이 많아 질 수록 더 많은 Array를 요구되어진다.

전체 Node 갯수를 구하는 방법은 다음과 같다.

Level 0 1 2 3 4 5
Num 1 , 2 , 4, 8 , 16, 32

이곳에 간단한 규칙이 존재하고 있으며, 예를 Level 4의 Node는 16 이고, 그 이전 Node 합은 (1+2+4+8)=15,
즉 현재 Node -1 은 이전 Node의 합과 동일하다. 그러므로 다음 Node -1하게 되면 된다.

i = Node의 Level

Number of Node = 2^(i+1) -1 , N 은 Tree의 Level의 수
Left Node = 2i+1
Right Node = 2i+2
Parent Node = (i-1)/2

https://en.wikipedia.org/wiki/Binary_tree
https://en.wikipedia.org/wiki/Binary_search_algorithm

3. Binary Tree 일반기능

Searching

key 값이 동일하면, 현재 Node ,
key < 현재 node.key 작을 경우, left 진입
key > 현재 node.key 클 경우 right 진입

Insertion

Node가 Empty일 경우, 마지막 Node일 경우, 삽입
key < 현재 node.key 작을 경우 , left 진입
key > 현재 node.key 클 경우 , right 진입

Search와 동일하지만, 삽입기능만 추가.

Deletion

기본은 위의 Searching 으로 동일하게 삭제할 Node를 찾는다.
Node를 삭제 할경우 세가지 사항을 고려한다.
one child는 left node or right node를 말하며, sub-left-tree or sub-right-tree도 가능

1. 삭제할 node가 단말 , no child 일 경우
1. Searching 통하여 삭제할 Node Data 찾음
2. 문제없이 삭제 가능

2. 삭제할 node가 one child 일 경우
1. Searching 통하여 삭제할 node를 data 찾음
2. 삭제할 node의 삭제이전 node를 저장
3. 삭제할 node는 link를 끊고 삭제
4. 삭제이전 node에 child node 연결

3. 삭제할 node가 two child 일 경우
1. Searching 통하여 삭제할 node를 data 찾음
2. 삭제할 node의 삭제이전 node를 저장
3. 삭제할 node 값과 유사한 값을 찾음 (둘 중 선택 A or B)
A. left-sub tree에서 가장 큰 값의 node 를 찾아 선택
B. right-sub tree에서 가장 작은 값의 node 를 찾아 선택

4.1 위의 선택된 node가 last node 일 경우 (no child)
A. 삭제이전 node에 선택된 node 연결
B. 선택된 node에 삭제할 node left,right 연결
C. 삭제할 node 삭제 .

4.2 위의 선택된 node가 sub-tree 일 경우 (sub-tree root)
A. 삭제이전 node에 선택된 node를 연결
B. 삭제할 node를 삭제
이 경우는 one child sub-tree 구조이기에 상위 2번째 방법과 동일 **

**주석
Binary Search Tree 구조상 아래의 구조밖에 될 수 밖에 없다.
A에서 가장 큰 값은 sub-tree node일 경우 right child 없다.
B에서 가장 작은 값은 sub-tree node 일 경우 left child 없다.

아래의 그림을 참조 이해하기 쉽다.
http://www.algolist.net/Data_structures/Binary_search_tree/Removal
http://stackoverflow.com/questions/8292661/how-to-delete-a-node-with-2-children-nodes-in-a-binary-search-tree

Traversal

Search와 Traversal 다르며, 기존에 존재하는 Data에 방문하는 순서를
어떻게 정하는지를 결정한다.

1. Depth-first Search (DFS, 깊이 우선 탐색)

pre-order : 처음에 방문하면 pre-order
in-order : 중간에 방문하면 in-order : BST Tree에서 사용
post-order : 나중에 방문하면 post-order

A. Pre-order

Visit current Node and Get Data
Traverse the left subtree by recursively
Traverse the right subtree by recursively

B. In-order
일반적인 Binary Search Tree에서 많이 사용한다.
왜냐하면, 최소값 부터 정렬이 가능하다.

Traverse the left subtree by recursively
Visit current Node and Get Data
Traverse the right subtree by recursively

C. Post-order

Traverse the left subtree by recursively
Traverse the right subtree by recursively
Visit current Node and Get Data

https://en.wikipedia.org/wiki/Depth-first_search

2. Breadth-first search (BFS, 너비 우선 탐색)

Level order

Queue에 방문할 Node를 넣는다.
방문할 Node를 Queue에서 얻는다.
Left 방문하고 Child Node가 있을 경우 이를 Queue에 삽입.
Right 방문하고 Child Node가 있을 경우 이를 Queue에 삽입.
Queue Empty가 될때까지 2번을 반복

https://en.wikipedia.org/wiki/Breadth-first_search

Binary Traversal

https://en.wikipedia.org/wiki/Tree_traversal
https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C **

Binary Search Tree
https://en.wikipedia.org/wiki/Binary_search_tree
http://robodream.tistory.com/181
http://web.skhu.ac.kr/~cyberci/program/view/view_13.htm

10/21/2016

이산수학 정리 (수정중 )

이산수학을 다 정리할 생각은 없으며, 내가 필요하다 싶은 지식만을 정리를 하겠다.
다른 관련내용은 이산수학책을 참조하자.

나의 관심은 수열과 계승 및 즉 수의 나열하는 방식이다.

계승 (팩토리얼)

수학에서 계승이라고 하며, 영어로 팩토리얼이라고 한다. 처음 프로그래밍에서 많이 쓰이는 수의 형태이다.
연속된 자연수를 사용하여 차례 곱을 하면된다.

N! 으로 표시
5! = 5x4x3x2x1 , 1씩 감소하면서 마지막값이 1일 될때까지 곱을 하는 방식

아래는 팩토리얼의 의 수열 (1! ~ 6! 까지)
1 1 2 6 24 120 720
0! 1! 2! 3! 4! 5! 6!

당연하겠지만, 이전 수열의 곱에 현재 팩토리얼곱은 현재값가 동일

24*5 = 120

  https://ko.wikipedia.org/wiki/%EA%B3%84%EC%8A%B9
  https://en.wikipedia.org/wiki/Factorial

순열의 공식

수학에서 순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다.
이는 치환이라고도 하며, 문자열로 치면 순서가 바뀌는 anagram이라고도 할 수 있다.

1. n개의 원소의 k-순열

n개의 원소 중에 k개의 순열을 나열하는 방법의가지수를 말한다.
이때 당연히 k개의 순열은 k< n 작어야 겠다.
만약 노래 여섯곡 가운데, 세 곡을 순서대로 배정하는 방법의 총수를 계산하는 방법

P(6,3) = 6 x 4 x 3 = 120
P(n,k) = n (n-1) (n-2) ... (n-k+1) = n! /( n-k)!

https://ko.wikipedia.org/wiki/%EC%88%9C%EC%97%B4

수열의 공식

1. 일반 수열의 합

1 ,2 3, 4, 5 ,6 7 ... (n-1) + n

항상 첫항과 끝항을 더하면 n+1 이것이 n번 반복이 되니,
n(n+1) /2

https://ko.wikipedia.org/wiki/%EC%88%98%EC%97%B4

2. 등비수열 의 합

1, 2, 4 , 8 , 16 ,32 , 64

An = ar^n-1 (A: 1, R:2 , N:1 부터 시작 )
Sn = a + ar + ar^2 + ar^3 ... + ar^n

https://ko.wikipedia.org/wiki/%EB%93%B1%EB%B9%84%EC%88%98%EC%97%B4

이항계수 및 피보나치 수열

https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98
http://wiki.mathnt.net/index.php?title=%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98%EC%99%80_%EC%A1%B0%ED%95%A9

알고리즘_대회에_필요한_수학

내게 꼭 필요한 사이트 였으며, 까먹었던 수학을 다시 상기해준 사이트이다. https://algospot.com/wiki/old/561/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EB%8C%80%ED%9A%8C%EC%97%90_%ED%95%84%EC%9A%94%ED%95%9C_%EC%88%98%ED%95%99

국내 이산수학 공개강의들

강원대 이산수학
http://www.kocw.net/home/search/kemView.do?kemId=309519

충북대 이산수학 집합론
http://www.kocw.net/home/search/kemView.do?kemId=332498&ar=relateCourse

금오공과대 이산수학 이산수학
http://www.kocw.net/home/search/kemView.do?kemId=1127202&ar=relateCourse

10/20/2016

Google Interview 관련 후기 자료수집

1. 구글 인터뷰에 필요에 자료

갑자기 구글 리쿠르터가 또 인터뷰를 보자고 해서 아래와 같은 자료들을 모으며, 다음 부터는 코딩연습을 많이 하고 그래야 할 것 같다.

항상문제는 바쁠 때, 인터뷰 보자고 하는게 문제인 것 같으며, 시간은 꼭 2주이다.

Youtube로 관련 Tip 과 정보를 제공
  http://www.gamecodi.com/board/zboard.php?id=GAMECODI_Talkdev&no=2544

2. 구글 전체 인터뷰 과정 설명 수집

구글 인터뷰 전체과정
  https://zublog.wordpress.com/2011/12/29/%EA%B5%AC%EA%B8%80%EC%9D%B4-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EB%A5%BC-%EB%BD%91%EB%8A%94-%EB%B2%95/

알고리즘 인터뷰 준비법
  http://theyearlyprophet.com/interviews-101-preparation.html

3. 구글 On Site Interview 과정 설명

구글인터뷰 후기
  http://kenial.tistory.com/915
  http://www.gilgil.net/14060

구글 인터뷰 좋은 팁 및 관련사항
http://sv-archives.blogspot.kr/2016/01/blog-post.html
http://www.workingus.com/v3/forums/topic/%EA%B5%AC%EA%B8%80-%EC%9D%B8%ED%84%B0%EB%B7%B0-%EB%A7%88%EC%B3%A4%EC%8A%B5%EB%8B%88%EB%8B%A4-%EC%A4%91%EA%B0%84%EC%83%81%ED%99%A9/

4. 인터넷 코드 테스트 문제

구글 전화 인터뷰시 알아야 할 필수사항 Data structure 및 Algolithim

O notation 계산법
Stack , Queue 구현
Hash Table 구현
Tree 구현
Recursion 구현
Bit 조작 구현
Graphs , BFS, DFS

이전에 내가 정리한 자료구조
https://ahyuo79.blogspot.com/search/label/Algorithm

Google Interview 자료모음 사이트
https://www.careercup.com/page?pid=google-interview-questions

Google Interview 공유 및 연봉확인
https://www.glassdoor.com/Interview/Google-Interview-Questions-E9079.htm

현재 책으로 있으며, 관련예제 찾아서 보자
http://www.crackingthecodinginterview.com/

5. 인터넷 컴파일러

Web상에서 직접 코딩연습을 할수 있는 사이트로 컴파일러 기능제공
http://ideone.com/

10/19/2016

Big O 표기법 (O notation ) 명칭정리

1. O표기법 관련 영문 명칭 및 예제

아래의 Wiki에서 가져왔으며, 각 O표기법 마다 의 영어 명칭과 예제를 정확히 알기 위해 아래에 표시

솔직히 아래의 Notation을 전부 이해하지는 못하겠으며, 아직도 혼동이 되고 있다.
이는 알고리즘을 개별 알고리즘을 분석하면서 알아내야 겠다.

Notation	Name	Example
$O(1)$	constant	Determining if a binary number is even or odd; Calculating $(-1)^{n}$ ; Using a constant-size lookup table
$O(\log \log n)$	double logarithmic	Number of comparisons spent finding an item using interpolation search in a sorted array of uniformly distributed values
$O(\log n)$	logarithmic	Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a Binomial heap
$O((\log n)^{c})$ $\scriptstyle c>1$	polylogarithmic	Matrix chain ordering can be solved in polylogarithmic time on a Parallel Random Access Machine.
$O(n^{c})$ $\scriptstyle 0<c<1$	fractional power	Searching in a kd-tree
$O(n)$	linear	Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; adding two n-bit integers by ripple carry
$O(n\log ^{*}n)$	n log-star n	Performing triangulation of a simple polygon using Seidel's algorithm, or the union–find algorithm. Note that $\log ^{}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{}(\log n),&{\text{if }}n>1\end{cases}}$
$O(n\log n)=O(\log n!)$	linearithmic, loglinear, or quasilinear	Performing a fast Fourier transform; heapsort, quicksort (best and average case), or merge sort
$O(n^{2})$	quadratic	Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive implementation), Shell sort, quicksort (worst case), selection sort or insertion sort
$O(n^{c})$	polynomial or algebraic	Tree-adjoining grammar parsing; maximum matching for bipartite graphs
$L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ $\scriptstyle 0<\alpha <1$	L-notation or sub-exponential	Factoring a number using the quadratic sieve or number field sieve
$O(c^{n})$ $\scriptstyle c>1$	exponential	Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent usingbrute-force search
$O(n!)$	factorial	Solving the traveling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with Laplace expansion; enumerating all partitions of a set

전체적인 O표기법을 설명
  https://en.wikipedia.org/wiki/Big_O_notation

기본 O표기법 설명 및 복잡도 비교하는 법 설명
  http://web.mit.edu/16.070/www/lecture/big_o.pdf

쉽게 간단히 O표기법 설명
  https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

10/18/2016

Big O 표기법 (O notation ) 의 기본이해

1. O 표기법 (Big O notation) 기본 정보

O표기법으로 표시는 아래와 같이 세가지로 나눌수 있다.

최악의 성능 경우 (Worst-case analysis)
최고의 성능 경우 (Best-case analysis)
평균의 성능 경우 (Average-case analysis)

하지만, O 표기법은 표시할 때 에는 아래와 같이 최악경우를 생각하고 많은 관심을 가진다고 한다.

많은 알고리즘들이 실행 할 경우, 최악의 성능을 가지고 동작을 한다고 한다.
많은 알고리즘들이 최상의 경우를 가지고 분석을 하면, 별 도움이 되지 않는다고 한다.
평균의 경우, 이 평균을 정확하게 계산하기가 힘이 들며, 평균성능을 계산이 불가능할때도 있기 때문이다.
최악의 경우는 알고리즘의 성능의 한계를 표시해주며, 더 나쁘게 실행되지 않는다고 보장한다.

1.1 기본 표기법의 결론

보통 최악의 성능 경우 (Worst-case analysis)로 측정을 한다.

예외사항이 존재 - 평균 성능의 경우 (Average-case analysis)

예를 들면, 평균의 성능경우 근거로 해야 할 경우가 필요한데, 무작위 알고리즘들은
평균성능으로 해야한다고 한다. 왜냐하면, 일반적인 확률 원칙을 적용해야하기 때문이다.

그 대표적인 예로 Quick sort이며, 무작위 알고리즘으로, 평균성능(Average-case analysis)을 가지고 판단해야 한다고 한다.

아래사이트 가면, Worst-case analysis, Best-case analysis ,Average-case analysis 접근이 나온다.

https://en.wikipedia.org/wiki/Quicksort

참조: C로 구현한 알고리즘
https://en.wikipedia.org/wiki/Computational_complexity_theory#Best.2C_worst_and_average_case_complexity

2. Big O 표기법 과 시간복잡도의 관계

Big O 표기법 기반으로 시간의 복잡도를 알수 있으며, 이에 관련된 기본 규칙이 존재한다.
아래는 X축은 N번 말하며, Y축은 시간의 복잡도 (Time complexity) 를 표시를 해준다.
시간의 복잡도는 Big O 표기법 기준으로 나온 값을 말하며, Big O표기값과 동일하다고 생각하며 되겠다 하지만 아래와 같은 몇가지 규칙이 존재한다.

X축 O 표시법의 입력
Y축 O 표시법의 시간복잡도

상위 표로 알수 있는 것은 O표기법의 시간의 복잡도를 알수 있다.
간단히 보면, 1은 복잡하지 않지만, N! 과 2^N, N^2 복잡도가 복잡해지는 것을 알수 있다.

https://en.wikipedia.org/wiki/Time_complexity

2.1 시간복잡도의 기본규칙 (Time complexity's Rules)

Big O notation을 이용하여 Time complexity를 계산할 경우, 아래와 같이 기본 규칙들이 존재한다.

기본 규칙 1

O(1) : 일정시간 , 동일한 시간이 걸리는 작업은 O(c)가 되더라도 O(1)로 표시한다.

O(c) = O(1) 모두동일

기본 규칙 2

입력이 N번 Loop 작업이 3개가 있을 경우 이를 표시하면 O(3N), 이지만, 임의 상수 c는 아래와 같이 표시한다. ( T(n) =n 작업이 3개 이므로, c는 3)

O(cT) = cO(T) = O(T) 모두동일

기본규칙 3

더할 때에는 가장 큰것을 선택한다.
한작업이 O(N) 실행 후 다른 한 작업 O(N^2) 일 실행 될 경우, O(N^2)만 선택
이유는 아래에 설명

O(T1) + O(T2) = O( T1 + T2) = max( O(T1), O(T2) ) 동일

e.g O(N) + O(N^2) = O(N^2) 로 선택

기본규칙 4

곱을 할 경우, 좀더 간결하게 적용가능. 바깥 루프가 O(N1) 이고, 이를 T1이라고 하고,
안쪽 루프를 O(N2) 하고 이를 T2로 한다고 하면,

O(T1)O(T2) =O(T1 * T2) 동일

e.g O(N) * O(N) = O(N^2), O(N) * O(N-1) = O( N* (N-1) )

2.2 시간복잡도 규칙의 적용의 예 (Examples)

시간의 복잡도(Time Complexity) 규칙을 설명을 했고, 이를 이용하여 실제 작업에 적용하여 이 규칙의 원리에 대해 파악해보자.

예를 들면, 작업 A, B, C가 존재 한다고 하고 각각의 작업, 즉 Program의 Big O 표기법을 이용하여, Time Complexity를 측정을 해보자.

작업 A

O(3N^2) : 이중루프로 N번을 반복하는 작업이 존재하며, 이 작업이 3개일 경우

int i=0,j=0;
int test=0;

// 1번째 작업 , N *N 작업 
for (i=0;i< n; i++)
   for (j=0;j< n; j++)
       test++;

// 2번째 작업 
for (i=0;i< n; i++)
   for (j=0;j< n; j++)
       test++;

// 3번째 작업 
for (i=0;i< n; i++)
   for (j=0;j< n; j++)
       test++;

작업 B

O(10N) : N번의 반복하는 작업 존재하며, 이 작업 10개가 존재할 경우

int i=0;
int test=0;

// 1번째 작업 , N번 작업 
for (i=0;i< n; i++)
       test++;
// 2번째 작업 
for (i=0;i< n; i++)
       test++;

// 3번째 작업 
for (i=0;i< n; i++)
       test++;
....
// 10번째 작업 
for (i=0;i< n; i++)
       test++;

작업 C

O(10) : 항상 10번 반복하는 작업 존재. 이 작업이 1개 존재 할 경우,

int i=0;
int test=0;

// 1번째 작업  , 항상 동일 
for (i=0;i< 10; i++)
       test++;

위 전체작업을 표시 하면 아래와 같지만, 위의 기본규칙 1, 2, 3 정리하면 아래와 같이 정리된다.

전체 작업 A , B, C 가 존재하며 이 작업을 규칙을 사용하여 간소화해보자.
작업 C는 기본규칙의 1번의 동일 작업이다.
기본규칙 3번에 의해 MAX값만 사용 ( 간소화)
기본규칙 2번에 의해 앞에 상수는 의미가 없어진다.

O(3N^2 + 10N + 10) = O(3N^2) = O(N^2) 와 거의 동일

이 규칙에서 핵심이 되는 기본규칙 3번의 원리를 분석하고 넘어가겠다.

위와 같이 되는 이유를 개별작업시간과 전체작업시간을 백분율로 계산을 해보자.

(개별작업시간/전체작업시간) * 100

여기서 개별작업시간을 간단히 백분율로 분석을 해보자.

N=10일 경우,

작업 A 실행시간 = O(3N^2) / O(3N^2 + 10N + 10) * 100 = 73.2%
작업 B 실행시간 = O(10N) / O(3N^2 + 10N + 10) * 100 = 24.4%
작업 C 실행시간 = O(10) / O(3N^2 + 10N + 10) * 100 = 2.4%

N=100 일 경우,

작업 A 실행시간 = O(3N^2) / O(3N^2 + 10N + 10) * 100 = 96.7%
작업 B 실행시간 = O(10N) / O(3N^2 + 10N + 10) * 100 = 3.2%
작업 C 실행시간 = O(10) / O(3N^2 + 10N + 10) * 100 = 0.1% 이하

위와 같이 N이 증가 할수록 작업 A에 시간의 복잡도가 최대값인 작업 A에만 편중이 되는 것을 확인 할수 있다.

N 값에 증가 값에 따라 N의 복잡도가 N^2에 편중이 되므로, 다른 것들은 거의 무의미 해지기 때문에 이 규칙이 적용이된다.

O(3N^2 + 10N + 10) = O(3N^2) = O(N^2) 와 작업 A 거의동일

위와 같이 일반 작업처럼 기본공식 3 통해 단순화 시킬수 있겠지만, 위와 같이 N이 증가할 경우를 고려했기 때문에 단순화하여 가능하지만,

만약 정확한 비교와 다른 오차를 생각 한다면, 예를 들면 N의 값이 정해져 있다고 하고, 다항식의 늘어날 경우,
다른 작업 값도 무시할수는 없을 것이다.

2.3 시간복잡도 2번째 예제 (수열)

C로 구현한 알고리즘에서 삽입정렬을 보다가, 오랜만에 보니, 일반수학에 대해 잊어버려서
n + (n -1) + (n -2) + ... 1 합의 계산을 구하는 공식을 아래와 같이 적음

아래공식은 위의 합을 구할려면, 일반적인 규칙을 찾아야 하며,

기본 수열의 합 공식

가장 끝수와 가장 첫수를 더하면 항상 (n+1) 동일
위의 합의 전체 반복은 N이며, 2개짝으로 했기에, 2로 나눈다.

n (n+1)/2 : 1, 2, 3, 4, 5, .... n 의 합

아래에 예제에 적용

https://ko.wikipedia.org/wiki/%EC%88%98%EC%97%B4

아래의 예제는 원래 C로 구현한 알고리즘의 삽입정렬이지만, 간단하게 이해하기 쉽도록 표기
자세한내용은 책을 참조.

int SimpleTest ( int size)
{
   int i=0,j=0;
   int test=0;

   for(i=1; i< size; i++)
   {
     j= i-1;

     while(j>=0){
        test ++;        
        j--;
     }

   }

   return 0;
}

상위를 소스를 분석하여, 시간복잡도를 계산해보면, 바깥루프는 반복횟수가 (n-1) 안쪽 루프는 바깥루프의 의존적이다.

이제 바깥루프와 안쪽루프에 실제 값을 넣어 i, j에 i=1, j=0 부터 넣어 봤을때,
안쪽루프의 계산되는 부분(test++) 의 안쪽루프의 계산되는 부분의 반복횟수를이 직접 보자.

n : 바깥루프의 반복횟수, size

i j 반복횟수(계산되는부분)
1 0 1
2 1 2
3 2 3
4 3 4
5 4 5
(n-1) (n-2) (n-1)

안쪽루프의 계산되는 반복횟수를 분석을 해보면 1, 2, 3, 4 5 ,6 ~ (n-1) 증가되는 것을 알 수 있으며,
이는 수열과 동일구조이며 이것을 시간의 복잡도로 표시하면, 1 ~ (n-1) 합으로 표시가 가능하게되어진다.

수열의 합공식을 적용하면, (n-1)n/2 을 해주면 된다.
이를 간소화 하면, O((n^2)/2- n/2) 표시가 가능하며, 이는 O(n^2)와 동일하게 된다.

참조: C로 구현한 알고리즘
https://en.wikipedia.org/wiki/Time_complexity

2.4 시간복잡도 3번째 예제 (재귀함수 or LOOP )

LOOP와 사칙연산 간의 반복횟수 규칙

Loop와 사칙연산인 더하기/빼기/곱하기/나누기가 만날 경우의 각각의 규칙을 생각해보자.

N : N=2 이상의 변수
X : Loop의 최종 목표값 or 초기 값

Loop 와 + N 일경우, 곱하기로 변하지만, 반복횟수 X/N
Loop 와 - N 일경우, 나누기로 변하지만, 반복횟수 X/N
Loop 와 * N 일경우, 지수로 변하지만, 반복횟수 LogNX
Loop 와 / N 일경우, 로그로 변하지만, 반복횟수 LogNX

반복횟수가 동일한 이유는 Loop 는 무한이 아니라 유한으로 동작하며, 이를 Loop를 반복횟수 구하는 작업은 동일하다.

수열과 같이 증가 와 감수되는 규칙을 알고 배열 순서가 바뀌는 것을 알면 되겠다.

LOOP or 재귀의 세부 분석의 예제

값을 대입을 해보고 간단히 분석해보고 계산하자
우선 재귀들의 구성을 보면, input값에는 return value의 영향을 받지 않는다.
그래서 input 중심으로 분석한다.

개별 함수의 Time Complexity 계산을 해보자. T(n)으로 표시해도 좋다.
검증을 원하면, 전역변수를 넣어 count를 해서 점검을 해보자.

아래에서 재귀에서 O(1)은 재귀의 종료조건을 말하고, 이는 반복횟수에도 포함도 가능

재귀 함수-A (일반 LOOP)

Input n=5, 반복횟수 : n+1
Input 5, 4, 3, 2, 1, 0: -1
O(1) not working

O(n) = O(1) + O(n) = O(n) or O(n+1)
상위 규칙을 적용하면, O(n) 겠지만, 정확히 하기 위해서 O(n+1)

static int cnt=0;

int recursiveFun1(int n)
{
    cnt++; 

    if (n <= 0)
        return 1;   // +1
    else 
        return 1 + recursiveFun1(n-1);  //N
}

int loopFun1(int n)
{
    int i;
    
    for(i=n;i >0; i-=1  )
    {
        cnt++; //N
    }
 
    return 1;
}

재귀 함수-B (LOOP의 X/N의 예제)

Input n=15, 반복횟수 : n/5+1 = 4
Input 15 10 5, 0: -1
O(1) not working

O(n) = O(n)/5 + O(1) = 1/5* O(n) + O(1) = O(n)

static int cnt=0;

int recursiveFun2(int n)
{
    cnt++;
 
    if (n <= 0)
        return 1;                 //+1
    else
        return 1 + recursiveFun2(n-5);  //N/5
}

int loopFun2(int n)
{
    int i;
    
    for(i=n;i > 0; i-=5  )   //N/5
    {
        cnt++; 
    }
 
    return 1;
}

재귀 함수-C (LOOP의 LOGNX)

Input n=125, 반복횟수 : Log5(n+1) + 1 = 5
Input 125, 25, 5, 1 , 0
O(1) not working

반복횟수가 n+1 가 되는 이유는 5^0 = 1 도 포함해야 하기 때문

O(n) = O(Log5(N+1)) + O(1) = O(Log5(N+1))

static int cnt=0;

int recursiveFun3(int n)
{
    cnt++;

    if (n <= 0)
        return 1;      // +1
    else
        return 1 + recursiveFun3(n/5);  //Log5N
}

int loopFun3(int n)
{
    int i;
    
    for(i=n;i > 0; i/=5  )  //Log5N
    {
        cnt++; 
    }
 
    return 1;
}

재귀 함수-D (재귀의 확장성 과 등비수열 )

아래의 첫번째 함수와 재귀함수-A와 동일한 형태이지만, 2번째함수는 연속 2번 재귀호출하여 점점 2배씩로 확장하면서 커지는 구조이다.
재귀의 확장성을 알기위해서 등비수열과의 연관성도 알아두고, 어떻게 확장이 되어가는지 정확한 이해를 하자.

예를 들면, 재귀함수의 전체 반복횟수를 알아보기위해, 이 구조를 완전 2진 트리라고 생각하자.

시작조건 N=5 입력
종료조건 (N==0 이면 종료)
전체 반복횟수 (N+1) = 6 번

002 번 재귀호출 (처음호출)
004 번 재귀호출
008 번 재귀호출
016 번 재귀호출
032 번 재귀호출
001 번 재귀호출 ( 64개 중에 종료조건이 맞아 종료)

상위 형태는 등비수열의 형태이며, 이를 3배씩 변경하면 그 효과 역시 동일하다.
물론 위의 조건이 약간씩 상이하게 변경이 될 수 있지만, 그 근본은 동일하다고 생각한다.

- 등비수열의 구조 와 합의 공식

등비수열구조 : Sn = a + ar + ar^2 + ar^3 .. + ar^(n-1)
합의공식 : a(1-r^n) / (1-r)

- 1st 함수 분석

재귀함수-A 와 아래 첫번째 재귀함수는 동일한 구조이며, 이를 다시 한번보자.

Input n=5, 반복횟수 : n+1
Input 5, 4, 3, 2, 1, 0: -1
O(1) not working

O(n) = O(1) + O(n) or O(n+1)

- 2nd 함수 분석

두번째 재귀 함수호출수는 반복횟수 동일하지만 함수가 2배식 확장되어, 함수 종료 조건은 한번만 실행되어진다.

n=5 일 경우 , 반복횟수 : n+1

2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 1 = 63
O(1)
n은 감소하면서 두번식 확장하면서 커진다.

합의 공식 대입: (1-2^6)/(1-2) = -63/-1 = 63 (r=2 , a=1 , n+1 대입)

n=10 일 경우 , 반복횟수 : n+1

2^1 + 2^2 + 2^3 + 2^4 + 2^5 ... 2^10 + 1 = 2047

합의 공식 대입: (1-2^11)/(1-2) = -2047/-1 = 2047 (r=2 , a=1 , n+1 대입)

이공식을 다음과 같이 변경 가능하다.

O(n) = O(2^(n+1)) - 1

N 대신 2^(N+1)를 넣고 첫번째 재귀함수와 동일하게 반복횟수는 n+1 이다.

n을 5을 넣으면, 함수 호출수는 2^(n+1) -1 = 64 - 1번 = 63
n을 10을 넣으면 함수 호출수는 2^(n+1) -1 = 2048 -1 번 = 2047

- 3rd 함수 분석

세번째 재귀 함수호출수는 반복횟수 동일하지만 함수가 3배식 확장되어, 함수 종료 조건은 한번만 실행되어진다. .

n=5 일 경우 , 반복횟수 : n+1

3^1 + 3^2 + 3^3 + 3^4 + 3^5 + 1 = 364
O(1)
n은 감소하면서 3배식 확장하면서 커진다.

합의 공식 대입: (1-3^6)/(1-3) = -728/-2 = 364 (r=2 , a=1 , n+1 대입)

상위 공식을 아래와 같이 변경 가능하다.

O(n) = O(3^(n+1) - 1 ) / 2

n=5 ( 3^(5+1) - 1 ) / 2 = 364
n=10 ( 3^(10+1) - 1 ) / 2 = 88573

- 4th 함수 분석

네번째 재귀 함수호출수는 반복횟수 동일하지만 함수가 4배식 확장되어, 함수 종료 조건은 한번만 실행되어진다.

상위와 같은 등비수열의 합이며, 동일하게 아래와 같이 일반화하여 쉽게 구할수 있다.

O(n) = O(4^(n+1) -1 ) / 3

n=5 (4^(5+1 ) -1) / 3 = 1365
n=10 (4^(10+1) -1) / 3 = 1398101

static int cnt=0;   // 전역변수로 한번 점검해보자 

void recursiveFun4_1(int n, int m, int o)
{
    cnt++;
    if (n <= 0){
        return 1;
    }else{
        recursiveFun4_1(n-1, m+1, o);   // 동일한 함수를 1번 호출 1배식 확장 
    }
}

void recursiveFun4_2(int n, int m, int o)
{
    cnt++;
    if (n <= 0){
        return 1;
    }else{
        recursiveFun4_2(n-1, m+1, o);  // 동일한 함수를 2번 호출하여 2배식 확장 
        recursiveFun4_2(n-1, m, o+1);
    }
}

void recursiveFun4_3(int n, int m, int o)
{
    cnt++;
    if (n <= 0){
        return 1;
    }else{
        recursiveFun4_3(n-1, m+1, o);  // 동일한 함수를 2번 호출하여 3배식 확장 
        recursiveFun4_3(n-1, m, o+1);
        recursiveFun4_3(n-1, m, o+1);
    }
}

void recursiveFun4_4(int n, int m, int o)
{
    cnt++;
    if (n <= 0){
        return 1;
    }else{
        recursiveFun4_3(n-1, m+1, o);  // 동일한 함수를 2번 호출하여 4배식 확장 
        recursiveFun4_3(n-1, m, o+1);
        recursiveFun4_3(n-1, m, o+1);
        recursiveFun4_3(n-1, m, o+1);
    }
}

재귀 함수-E

기본적으로 재귀함수-B 와 동일 하지만, 안에 다른 작업이 포함이 되어있어 이를 계산해보자.

다시 재귀함수-B를 보자

Input n=15, 반복횟수 : n/5+1 = 4
Input 15 10 5, 0
work_1 8 (7.5) 5 3(2.5) 1 = 17

아래의 소스를 동작해보면 cnt 16 으로 마지막 0 에서 cnt는 동작이 안됨 (n=0)

O(n) = O(n)/5 + O(1) = O(n/5)+1 안에 다른 작업이 반복이 된다.

static int cnt=0;   // 전역변수로 한번 점검해보자 

int recursiveFun5(int n)
{
    int i;

    for (i = 0; i < n; i += 2) { //work_1 
        cnt++;
    }

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

http://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation

2.5 시간복잡도 4번째 예제

Big O 표기법이라는 것이 기본규칙을 사용하여 일반화하여 구성을 하면 정확한 측정은 힘들어진다.
하지만 기본규칙은 항상 모든 알고리즘에서 빠른 계산과 쉬운 계산을 목표로 생각으로 구성을 해야겠다.

Example-1

   x = n
   while ( x > 0 ) {
       x = x - 1
   }

n=5
input: 5 ,4 ,3 ,2 ,1

O(n)

Example-2

   x = n
   while ( x > 0 ) {
       x = x / 2
   }

n=8
input: 8 , 4 , 2 , 1

O(logN)

Example-3

   x = n
   while ( x > 0 ) {
      y = n
      while ( y > 0 ) {
          y = y - 1
      }
      x = x - 1
   }

n=5
input : (5,4,3,2,1) , (5,4,3,2,1) , (5,4,3,2,1), (5,4,3,2,1) , (5,4,3,2,1)

O(N^2);

Example-4

   x = n
   while ( x > 0 ) {
      y = n
      while ( y > 0 ) {
          y = y / 2
      }
      x = x - 1
   }

n=4
input : (4,2,1) , (4,2,1) , (4,2,1), (4,2,1) : O(LogN) 을 O(n) 반복

O(NLogN);

Example-5

   x = n
   while ( x > 0 ) {
      y = x
      while ( y > 0 ) {
          y = y / 2
      }
      x = x - 1
   }

n=4
input : (4,2,1) , (3,1) , (2,1), (1) : O(LogN) 을 O(n)반복

O(NLogN);

Example-6

   x = n
   while ( x > 0 ) {
      y = n
      while ( y > 0 ) {
          y = y - 1
      }
      x = x / 2
   }

n=4
input : (4,3,2,1) , (4,3,2,1) , (4,3,2,1) : O(n)을 LogN 만큼 반복.

O(NLogN);

Example-7

   x = n
   while ( x > 0 ) {
      y = x
      while ( y > 0 ) {
          y = y - 1
      }
      x = x / 2
   }

n=4
input : (4,3,2,1) , (2,1) , (1) : O(n)을 O(LogN)만큼 반복 ( O(n)의 값이 적용 )

O(NLogN);

Example-8

   x = n
   while ( x > 0 ) {
      y = n
      while ( y > 0 ) {
          y = y / 2
      }
      x = x / 2
   }

n=4
input : (4,2,1) , (4,2,1) , (4,2,1) : O(LogN)을 O(LogN)만큼 반복 (두번째 LogN은 동일)

O(LogLogN);

Example-9

   x = n
   while ( x > 0 ) {
      y = x
      while ( y > 0 ) {
          y = y / 2
      }
      x = x / 2
   }

n=4
input : (4,2,1) , (2,1) , (1) : : O(LogN)을 O(LogN)만큼 반복 (두번째는 LogN는 감소)

O(LogLogN);

https://www.quora.com/How-can-we-check-for-the-complexity-log-n-and-n-log-n-for-an-algorithm

3. O 표기법의 주요 함수 내용 정리

기본적으로, O표기법으로 알아내는 법은 Input을 넣어 대입하고 어떻게 동작이 되는지를 파악을 해보면 된다고 생각한다.
그리고 그 변화에 규칙성이 알아내어 규칙성을 찾아 일반적인 함수를 적용 할수 있다면 적용하는 것이다.
여기서 이산수학의 필요성이 필요한 것 같다.

(사실 고등학교 수학지식이면 충분한 것 같다)

3.1 일반적인 O 표기법

O(1) : 항상 일정한 시간을 갖는것을 의미한다.

아래와 같이 반복 routine이 있다 할지라도, 100 * 200에서 항상 동일하게 끝난다.
아래는 항상 일정한 시간을 갖는 routine이다.

아래 작업을 두개의 일정한 값을 유지하는 작업이 2개 ( if 와 for 반복문)

O(c)+O(1) = O(1) C는 100 * 200

int index = 5;
int item = list[index];
if (condition true) then
   perform some operation that runs in constant time
else
   perform some other operation that runs in constant time
for i = 1 to 100
   for j = 1 to 200
      perform some operation that runs in constant time

3.2 일반적인 반복 O 표기법

O(N) : n은 보통 n번의 반복이며, for or while loop로 생각하면되겠다.

int index = 5;
int item = list[index];

for i = 1 to n       
      perform some operation that runs in n time

O(N^2): n번을 반복을 하고 다시 n번을 반복 이중반복이라고 생각하면되겠다.

int index = 5;
int item = list[index];

for i = 1 to n      
   for j = 1 to n
      perform some operation that runs in n * n time

O(N^3): 쉽게 3중반복이라고 생각하면되겠다.

위와 동일 하며, 반복문이 하나 더 추가 될 뿐이다.

3.3 2의 지수 O 표기법

O(2^N): 2의 지수이며, input data set이 두배로 확장되는 것을 의미한다.

재귀함수로 2번의 재귀함수를 사용하여, 매번 input data set이 두배로 확장

int Fibonacci(int number)
{
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

아래의 피보나치 수열을 계산과정을 보면 2의 지수 형태로 진행이 되는 것을 알 수 있다.
예를 들면, number를 5를 넣으면, 두번을 매번 재귀를 매번 호출하고,
재귀된 함수도 1 값이 될때 까지 2번씩 반복이 된다.
이는 2의 지수 함수 동일하다.

아래의 예제를 보면 쉽게 이해가 간다.
https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

3.4 Binary Log 함수 O 표기법

O표기법에서 사용하는 일반적인 Log의 아래값은 2이며, Log 함수의 기본적인 성질을 알아두자.

지수와 Log의 관계

b^V = M 일 때 Logb(M) = V 된다.
b^0 = 1 이를 Logb(1) = 0 변환하면 Log Rule 1번

쉽게 생각하면 b의 지수의 값을 구하려는 함수라고 생각하면 된다.
현재 O 표기법에서는 b의 값은 2이다,
고등학교때, 그냥 Log하면 Log b는 10인 걸로 기억을 하는데 처음 혼동이 되어서 간단히 적어본다.

Log 기본규칙 (Rules)

logb1 = 0 , Logb(b) = b;
logb(mn) = logb(m) + logb(n)
logb(m/n) = logb(m) – logb(n)
logb(m^n) = n · logb(m)

4번 규칙처럼 Log 함수에서 M의 지수를 사용할 경우, N * logb(M) 변환이 가능하다.
아래내용은 로그함수의 기본정의 규칙을 정리 다시 복습 해보자.

기본로그함수내용
  https://en.wikipedia.org/wiki/Logarithm
https://en.wikipedia.org/wiki/Binary_logarithm

로그관련 기본공식
  http://mathbang.net/597
  http://www.purplemath.com/modules/logrules.htm

O(logN) : log는 2를 말하며, 보통 binary search or Binomial heap 말한다.

원리는 둘 중 하나를 선택하여, 지속적으로 찾아가고 호출하는 방식을 말한다.
Binary Search 와 Binary Traversal은 다르며, Binary Search인 경우는
보통 현재 노드를 비교하여, 저장될 노드를 비교하여 찾아가는 구조이기에,
둘중 하나만 선택하여 찾아 호출하는 구조

http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly

n/b^3 의 의미 부터 파악해보면, layer가 내려갈 수록 1/b씩 곱하는것이다.
이 전체를 순회를 한다고 가정하면, 마지막 layer에 도착하기 위해서는 n/b^3의 확률이 걸린다. N=8이다.

O(NlogN) : log는 2를 말하며, LogN에 N번의 반복을 하는 것 같다.

LogN과 기본 원리와 비슷하지만, 아래와 같이 모든 Tree를 순회를 하게되면,
더 할 수 있겠다. 그리고, Log에서 덧셈을 곳셈으로 변환하고, 그 곳셈에서 나온값을
N의 지수가 나오기때문에 아래와 같이 간단히 정리를 할 수 있겠다.

= (log n+log(n-1)+...+log 2)
= (log n+log(n-1)+...+log 2)+(log n+log(n-1)+...+log 2)
= O(n*log n)

https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC
https://en.wikipedia.org/wiki/Heapsort
https://www.quora.com/How-can-we-check-for-the-complexity-log-n-and-n-log-n-for-an-algorithm

피드 구독하기: 글 ( Atom )