알고리즘 용어

1. In-place algorithm (인플레이스 알고리즘)

인플레이스 알고리즘(In-place) input을 어떤 보조의 데이터구조 사용없이 변경이되는 알고리즘을 말한다.
하지만, 작은 용량의 여분의 공간은 보조의 공간을 허용하는 편이다.
한마디로,  알고리즘을 위해서 메모리공간의 사용을 최대한 적게 사용하는 것이 목적이다.


아래의 wiki의 예제를 보면 input 배열을 reverse 두개의 함수가 존재한다.

  https://en.wikipedia.org/wiki/In-place_algorithm

• reverse function 

1. reverse는 Array이 즉, 메모리에 동일하게 할당한다
2. Time complexity O(n) = T(n) = n

• reverse_in_place function 

1. 기존의 Array에서 swap하면서 변경을 한다.
2. Time complexity O((n-1)/2) = T((n-1)/2) = n


상위 두함수를 비교를 해보면,

reverse 함수는 array를 reverse하기 위해, 동일하게 memory를 할당하여 두배를 사용한다.
reverse_in_place 의 경우는 input의 array를 이용하고, swap을 위한 변수만을 이용하여 이를 memory의 최소사용을 한다.


이 알고리즘과 반대되는 알고리즘은 not-in-place or out-of-place 라고 한다.


2. Divide and Conquer algorithm (분할 정복)

이 알고리즘의 목표는 복잡한 문제를 지속적으로 작은 문제로 분할을 하면서 해결하면서 해결을 하려고 하는 것이다.
이 복잡한 문제에서 분할(Divide)을 진행하면서 작은문제로 변경을 하고 이를 정복(Conquer), 즉 해결해 나가는 방식이다.

결론적으로 보면 top-down 방식으로 문제를 해결해 나간다고 생각하면 되겠다.

예를 들어보자면 Quick sort 인경우 data중에서 pivot 선택하여 기준을 정하고 item들을 pivot과 비교하여 위치변경한다
이것이 작은문제로 선정한것이다. 그리고, 매번 pivot정하고, 정렬할 범위를 정하고 위작업을 반복한다.

  https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%A0%95%EB%B3%B5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
  https://en.wikipedia.org/wiki/Divide_and_conquer_algorithm


3. 재귀 (Recursion)

자료구조와 알고리즘에서 흔히 많이 사용되는 방식이며 이는 많은 장점과 단점을 포함하고 있다.

• 기본동작방식 

Function 안에 Input을 변경하여 자신을 재호출하고,
Return 값을 받아 계산하여, 적용을 한다.


3.1 일반 재귀의 장점

흔히들 O(n) 같은 것을 O(1)으로 변경이 가능하다.
(한 함수내에서 보면 그렇지만 전체적으로 보면 O(n) 반복문인것은 동일하다)

함수의 내부 Stack를 기본적으로 이용하기에 Stack의 특성가진 LIFO Programming 쉽게 이용 가능하다.
상위 Divide and conquer algorithm에 적용이 쉽게 가능하며,
Dynamic programming에서 보면, 이는 Top-down 접근이나, Bottom-Up 접근이 용이하다.

3.2 일반 재귀의 단점 

함수의 내부 Stack를 이용하기때문에 사용량이 증가하면 Stack의 overflow는 발생 가능성이 높고,
성능이 저하되며, 속도역시 떨어질것이다.
그리고, 위에서 언급했듯이 지속적으로 공간이 두배식 확장되며서 Memory 문제도 발생한다.

  https://en.wikipedia.org/wiki/Recursion       
  https://ko.wikipedia.org/wiki/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98

• 공간문제 (Space complexity)

Function 안에서 자신을 재 호출하고 그 Return값을 기다리기 때문에 ,예를 들면,
1st function , 2nd function , 3rd function 호출 된다고 하자.
1st는 2nd을 Return을 , 2nd는 3rd의 Return을 기다려야 하기 때문에
함수의 사용공간 및 함수 내부 Stack 은 지속적으로 확장이 된다.
 

3.3 꼬리재귀 (Tail Call or Tail Recursion)

• 일반재귀의 특성 

위에서 설명한 재귀의 기본특성을 가지고 있지만, 재귀와 꼬리재귀의 차이는 무엇일까?

일반적으로, 함수를 호출을 하면 위에서 설명했듯이 함수를 호출하기 위해 call stack 이 존재한다.
그리고, 함수가 호출 되고 종료가 되면, CPU는 이 주소를 보고 원래 호출 장소로 상태로 되 돌아간다.
이를 call stack이라고 한다. Function, 함수들을 위한 stack인 것이다.


기본 Process 구조 or Program의 구조는 아래와 같이 구성이 된다.

1. CODE 영역
2. DATA 영역
3. STACK 영역
4. HEAP  영역

그리고, DATA 영역에는 초기화된 전역변수(bss)와 비초기화된 전역변수 존재하며,
STACK 영역에는 함수의 argument와 내부변수 및 위의 call stack이 저장이 된다.

HEAP 아시다시피 malloc 으로 잡힌 영역으로 말하지만,좀 더 깊이 들어가면 이부분도 복잡해진다.
(이부분은  추후 시간이 된다면 설명하겠다)

*참고사항

link script 에서 개별영역의 특성을 살펴볼수 있다.
본인이 좀더 깊게 공부하기를 원한다면, ARM용 ABI (aplication binary interface)를 한번 보기를  권한다.

  https://sourceware.org/binutils/docs/ld/Scripts.html#Scripts

• 꼬리재귀의 특성 

일반 재귀는 이 STACK 영역을 이용을하며, stack 관련 programming도 쉽게 가능하다.
일반재귀와는 다르게 꼬리재귀는 이 call stack이 매번저장할 필요가 없다고 한다.

1. 사실 내부적으로 어떻게 저장하고 어떻게  동작하는지 너무 궁금했다.
2. 왜 opimization 필요한가 ? 

원문)
For tail calls, there is no need to remember the place we are calling from – instead, we can perform tail call elimination by leaving the stack alone (except possibly for function arguments and local variables[3]) and the newly called function will return its result directly to the original caller.

간단히 해석하자면, 꼬리재귀는 call stack 필요는 없지만, 대신에  stack을 남기면서 꼬리재귀제거(tail call elimination) 수행을을 한다고한다. 이 stack에는 함수의 argument와 local variable을 제외되었다고 한다. 그리고, 내부에서 새롭게 호출되어지 함수는 결과 값을 돌려주는데, 이 것은 원래의 함수에 집적에 돌려준다고 한다.

이는 일반재귀와 동작방식이 근복적으로 다르며, 무작정 메모리공간을 두배식확장해가는 것이 아니라,
Tail call elimination을 위해 별도의 메모리 구성하며 호출하는 것이다.
이는 memory 절약뿐만 아니라, 속도에도 크게 향상을 보일 것이다.

아래의 사이트 해석대로라면, 일반재귀처럼 꼬리재귀는 막복사하여 만들어내지는않는 것 같다.

  https://en.wikipedia.org/wiki/Tail_call     ( Description 보면 자세한 설명)

• 사용예제 사이트 

본인은 간단히 함수 구현만 했으며,  TEST를 일일이 못했지만, 아래에 사이트들에서
너무자세히 잘해주었기에 그냥 TEST를 하지 않기로 하였다.

  http://yumere.tistory.com/69
  http://bozeury.tistory.com/96
  http://hanmomhanda.github.io/2015/07/27/%EC%9E%AC%EA%B7%80-%EB%B0%98%EB%B3%B5-Tail-Recursion/

• 관련 구현 

4. 알고리즘의 성능측정 

알고리즘의 성능측정을 객관적으로 표시하기 위해서 Big-O, Little-O, Theta, Omega, 기타 같은 방법이 존재하지만,
가장 많이 사용되는 것은 Big-O이며, 이 기준으로

우선 Time complexity가 성능의 우선순위에서 측정하기도 쉽고, 알기도 쉽다.

이를 먼저생각 한 후 그 후 Space complexity를 두 번째 조건으로 측정하는 것 같다. 

물론 Memory에 따라 변경이 될수 있겠지만, 대체적으로 그렇게 되는 것 같다. 

• Time complexity ( 시간의 복잡도)

이전에도 설명했듯이 Big O notation 기반으로 대부분 Worst Case 기반으로 측정을한다.

O notation 과 Time complexity에 관련 내용을 보면 쉽게 이해를 할 수 있다. 

• Space complexity (공간 복잡도)

Algorithm에서 Time complexity 이외에도 Space complexity도 존재하지만,
정확한 Memory의 사용량을 측정하기는 힘들다.
가장 간단한방법은 process의 전체 memory 사용량을 아는 것이겠지만,
이는 정확하지도 않고, 분석하기도 그렇다.
정확한 공간 복잡도는 별도의 Debugging Tool이 필요하며, 그나마,

공간복잡도를 쉽게 계산가능 한것은 함수 호출 횟수를 계산 할때의 Memory 증가성이다.
일반 재귀인 경우 Time complexity를 Space complexity로 변경이 가능하며
이를 time-space-tradeoff 말하는 것 같다.

  https://en.wikipedia.org/wiki/DSPACE 
  http://www.leda-tutorial.org/en/official/ch02s02s03.html