피보나치 수열 실현 - 귀속, 교체, 수조, 대열

1. 귀속
효율이 낮아서 마지막 수를 제외하고는 매 수를 몇 번씩 중복 계산한다

   1: // 

   2: public static int Fib1(int n)

   3: {

   4:     if (n < 3)

   5:     {

   6:         return 1;

   7:     }

   8:     else

   9:     {

  10:         return Fib1(n - 1) + Fib1(n - 2);

  11:     }

  12: }

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }
2. 교체
최고 효율, 시간 복잡도 O(n), 공간 복잡도 O(1)

   1: // 

   2: public static int Fib2(int n)

   3: {

   4:     if (n < 3)

   5:     {

   6:         return 1;

   7:     }

   8:     else

   9:     {

  10:         int first = 1;

  11:         int second = 1;

  12:         int temp = 0;

  13:  

  14:         for (int i = 0; i < n - 2; i++)

  15:         {

  16:             temp = first + second;

  17:             first = second;

  18:             second = temp;

  19:         }

  20:         return temp;

  21:     }

  22: }

3. 배열
효율은 보통이고 귀속보다 빠르며 시간 복잡도 O(n), 공간 복잡도 O(n)

   1: // 

   2: public static int Fib3(int n)

   3: {

   4:     List<int> list = new List<int>();

   5:     list.Add(1);

   6:     list.Add(1);

   7:     int count = list.Count;

   8:  

   9:     while (count < n)

  10:     {

  11:         list.Add(list[count - 2] + list[count - 1]);

  12:         count = list.Count;

  13:     }

  14:  

  15:     return list[count - 1];

  16: }

4. 대기열
시간 복잡도 O(n), 공간 복잡도 O(1)

   1: // 

   2: public static int Fib4(int n)

   3: {

   4:     Queue<int> queue = new Queue<int>();

   5:     queue.Enqueue(1);

   6:     queue.Enqueue(1);

   7:  

   8:     for (int i = 0; i <= n - 2; i++)

   9:     {

  10:         queue.Enqueue(queue.AsQueryable().First() + queue.AsQueryable().Last());

  11:         queue.Dequeue();

  12:     }

  13:     return queue.Peek();

  14: }