[coding-interview : 002] Big-O notation

Big-O 계산하는 방법 

- 우선, 어디까지나 대략적인 계산이지 정확한 시간을 측정하는 척도는 아니다.

- 데이터 수가 적다면 무슨 알고리즘이든 빠를 것이다. 알고리즘간 차이를 느끼려면 데이터의 개수가 많아져야한다. 그런데.. 데이터가 많아질수록 O(.)는 커진다. 때문에 O(n^2)과 O(n+n^2)는 큰 차이가 없다. (쉽게 예시를 들자면 1억개의 데이터에 하나의 데이터를 더한다고 해서 체감할 수 있을 정도의 변화가 일어나지 않는다는 것이다. 그래서 일반적으로 constant - 상수 부분은 Big-O notation 에서 빼버린다.)

First step >> N 정하기

In general : 

n개의 elements를 가진 array가 있을 때, logic상 각 element를 한 번씩만 체크한다면, O(n) 으로 n에 linear 하다고 할 수 있다. 

Linked List : 각 node의 개수가 n이 된다. 

Data type : bits의 개수이다. 

Hash table : number of entries (여기에서 entries가 정확하게 의미하는 바가 뭔지를 잘 모르겠다.)

Second step >> operation 체크 

After determining what n means in terms of the input, you must determine how many operations are performed for each of the n input items. 

n이 정해졌다면, 알고리즘을 체크해야 한다. insertion이 몇 번 일어나는지, creating 작업이나 deletion이 몇 번 발생하는지 등등.. Big-O notation 상에서 이 모든 작업들은 같은 중요도로 취급된다. 

예를 들어서 음수가 아닌 정수들로만 이루어진 array 하나를 받아서, 그 array의 max값을 return하게 하는 함수가 있다고 가정해보자. 

이 함수는 두 가지 방법으로 만들 수 있다. 데이터 하나하나의 값을 다른 하나의 값과 비교하면서 max값을 찾아내는 방법, 그리고 하나의 array를 동일한, 그러나 다른 방향으로 움직이는 array로 순차적으로 비교하는 방법이다. 

첫번째 케이스는 한 번의 input작업 (initializing)이 필요하고, 그리고 전체 array를 한 번 훑기 때문에 Big-O notation으로는 O(n)이 된다.

            n의 개수에 비례해서 작업 시간도 커지기 때문에, linear하다고도 한다. 

두번째 경우, 한 번의 loop와 다른 한 번의 loop가 같이 있기 때문에, n은 loop문의 개수만큼 지수승으로 증가하게 된다. 

      예를 들어서 input이 5개의 elements를 가진 하나의 array라면, 첫번째 for loop문이 돌때마다 두번째 for loop문은 전체를 훑게 된다. 

      0  0          1   0          2  0          3  0          4  0          5  0

      0  1          1   1          2  1          3  1          4  1          5  1

      0  2          1   2          2  2          3  2          4  2          5  2

      0  3          1   3          2  3          3  3          4  3          5  3

      0  4          1   4          2  4          3  4          4  4          5  4

--------------------------------------------------------------------------------------------- 그래서 두번째 케이스의 Big-O notation은 O(n^2)이다. 

     ↑   ↑

   first   second

for loop  for loop 

원래는 non-negative 조건이 있기 때문에, 각 element가 음수인지 아닌지를 판별하는 부분도 있어야 하는데.. 어차피 +1이라서 Big-O notation상에서는 O(n+1)이나 O(n)이나 종종 같게 취급되므로 쓰지 않았다. 

그러므로 현업자들은 전자의 알고리즘을 선택할 것이다. 굳이 두 번째를 반드시 써야 할 필요성이 없는 이상.. O(n)이 좋은 수치라고 볼 수는 없으나, O(n^2)은 커도 너무 크기 때문. 

 

Big-O Analysis in Action

n : the number of elements in an array

CompareToMax 라고 부르는 예시와

/* Returns the largest value in an array of non-negative integers */  int CompareToMax(int array[], int n)  {       int curMax, i;      /* Make sure that there is at least one element in the array  */      if (n <= 0)            return -1;     /* Set the largest number so far to the first array value. */     curMax = array[0];    /* Compare every number with the largest number so far */    for (i = 1; i < n; i++) {           if (array[i] > curMax) {                  curMax = array[i];           }  }

이 함수에서 array의 element 하나는 모두 한 번씩은 max value와 비교가 되어진다. n번의 examinations이 되는거다. O(n) 또는 linear time이라고 한다.

이 함수는 Best, Average, 그리고 worst case 모두 O(n)으로 같다.

CompareToAll 이라 부르는 예시를 보자.

/* Returns the largest value in an array of non-negative integers */  int CompareToAll(int array[], int n)  {        int i, j;        bool isMax;        /* Make sure that there is at least one element in the array. */        if (n <= 0)            return -1;        for (i = n-1; i > 0; i--)   {            isMax = true;            for (j = 0; j < n; j++) {                  /* See if any value is greater. */                  if (array[j] > array[i])   {                         isMax = false;     /* array[i] is not the largest value. */                         break;                  }              }              /* If isMax is true, no larger value exists; array[i] is max. */              if (isMax) break;       }       return array[i];  }

이 함수는 O(n^2)이다. 즉, array의 크기가 커질수록 CompareToAll의 비교 횟수는 CompareToMax 대비 기하급수적으로 증가한다.

이 함수는 best에선 O(n)이지만, worst case는 O(n^2)

Big-O notation 상에서는 worst case (최악의 경우) 와 best case (최고의 경우)를 가정해서 계산을 낸다. 

예를 들어서 입력받은 array에서 23이라는 숫자를 찾는다고 해보자. best case의 Big-O는 O(1)이다. array상의 element를 딱 한 번 집었는데, 바로 그게 23이었더라..하는거였다. 물론 비현실적이다. worst case는 전체 array를 훑는 것으로, array의 가장 마지막 element로 23이 있었을 때를 말한다. Big-O notation은 O(n)이 된다. 

이런식으로 best, worst case를 모두 가정하고, 최대한 그 둘 사이를 가깝게 만드는게 알고리즘을 효율적으로 돌리는 것이기도 하다.. 

그렇다면 Big-O는 어떻게 계산할까?

1. input이 뭔지, n이 뭘 대표해야 하는지를 알아내고

2. 알고리즘 상에서 operation이 몇 번 일어나는지 표현하고 

3. 모두 삭제하자. 가장 큰 값만 제외하고

4. 모든 constant 요소를 제거하자

아래로 내려갈수록 비효율적인 (computational cost가 매우 비싼..) 알고리즘이다.

 - O(log n) : An algorithm is said to be logarithmic if its running time increases logarithmically in proportion to the input size.   log 10 = 1

 - O(n) : A linear algorithm's running time increases in direct proportion to the input size.                 

 - O(n log n) : A superlinear algorithm is midway between a linear algorithm and a polynomial algorithm.          10 log 10 = 10 

 - O(n^c) : A polynomial algorithm grows quickly based on the size of the input.                                          10^2 = 100

 - O(c^n) : An exponential algorithm grows even faster than a polynomial algorithm.                                     2^10 = 1,024

 - O(n!) : A factorial algorithm grows the fastest and becomes quickly unusable for even small values of n.         10! = 3,628,800

--------------------------------------------------------------------------------------------------- from [Programming interviews exposed]

아래는 SWE 유투브 동영상 강의에서 가져온 것

https://www.youtube.com/watch?v=waPQP2TDOGE&t=644s

O(n)   "Linear time"  What is n?  - string length   - total tree nodes   - array size    etc..

O(log n)   "Logarithmic time"   - Normally log base 2. But doesn't really matter  our question : "What must I power my base (of 2) by to get n?"  So log(16) = 4.    Why?    2^4 = 16      "You see? Halving"

O(n * log n)  - What does this mean?      Fast sorting       - Merge sort      - Quick sort

O(n^2)  "n-squared"    - (in general) Naive solution   - Naive Sorting Algorithms      - Bubble sort      - Selection sort      - Insertion sort   O(n^2 / 2) = O(1/2 * n^2) = O(n^2)

O(2^n)   "Exponential time"   Backtracking problems     - subsets

O(n!)     "n-factorial"  Permutation

Memory Footprint Analysis

Memory use is sometimes as important as running time, particularly in constrained environments such as mobile devices.

In some cases, you will be asked about the memory usage of an algorithm. For this, the approach is to express the amount of memory required in terms of n, the size of the input, analogous to the preceding discussion of Big-O runtime analysis. 

The difference is that instead of determining how many operations are required for each item of input, you determine the amount of storage required for each item.

Other times, you may be asked about the memory footprint of an implementation. This is usually an exercise in estimation, especially for languages such as Java and C# that run in a virtual machine. Interviewers don't expect you to know to the byte exactly how much memory is used, but they like to see that you understand how the underlying data structures might be implemented. 

If you're a C++ expert, though don't be surprised if you're asked how much memory a struct or class requires -- the interviewer may want to check that you understand memory alignment and structure packing issues.