Big O의 개념, 유형, 계산 원칙 그리고 의미

좋은 코드란?

• 좋은 코드란 가독성이 좋거나 확장성이 있는 것을 의미한다. 확장성은 다시 시간 복잡도와 공간 복잡도 관점에서 볼 수 있는데, 두 관점은 상충하기 때문에 하나를 얻기 위해선 하나를 희생해야 한다.
• Big O는 확장성과 관련되어있다.
• 확장성이 항상 옳은 것이 아니며 빠른 행동이 중요한 스타트업의 경우 가독성을 우선하기도 한다.

Big O란?

• 확장 시 얼마나 시간이 더 오래 걸리는지 측정하는 지표가 Big O다. 걸리는 시간 그 자체가 중요한 것이라기 보다는 얼마나 더 느려지는 가에 초점을 맞추면 되겠다.

Big O의 유형

• Big O의 유형은 여러가지가 있다. O(1), O(log N), O(n), O(n log(n)), O(n^2), O(n!)가 있다
• To review what I learned today, 
  O(n) is linear time. The more input you have, the more it takes time
  O(1) is constant time. You only need to perform nth. 
  O(n^2) is quadratic time. This takes all pairs of array such as loop nested in loop. This increases time significantly.
  O(n!) is factorial time. You are adding a loop for all the elements. This is really bad one.
  

Big O를 계산하는 원칙

1. 최악의 케이스를 고려하라 : 반복문을 돌릴 어레이 요소 10개 중 5번만 돌아도 결과를 얻을 수 있더라도, 10번째까지 고려해야 최악의 케이스를 고려할 수 있다.
2. 상수는 무시하라 : item[0] + item[1] 등을 계산하는 코드, 즉 O(2)와 같은 Big O는 다른 유형에 비해 영향력이 낮기 때문에 무시해도 된다
3. 인풋에 따라 달라지는 결과를 고려하라 : 만약 어레이를 2개 받는 함수일 경우, 이 어레이에 대한 루프가 각자 돌 경우 O(a + b)가 되지만, 하나의 어레이 루프 안에 다른 어레이 루프를 돌릴 경우 O(a * b)가 된다. 어떻게 활용하느냐에 따라 Big O의 유형이 달라진다.
4. 덜 중요한 것들은 무시해라 : 2번 원칙과 유사하다. 만약 O(x^2 + 3x + 100)이 있다면 3x와 100은 무시해도 된다. x^2는 제곱으로 커지는 반면, 3x는 3배수밖에 커지지 않고 100는 변하지 않는다. 

그래서 Big O가 어떤 의미를 가진건가?

Big O는 경제적 이윤을 창출하는 지식이다

• Big O를 통해 공간 복잡도와 시간 복잡도를 고려할 수있게 된다. 메모리와 시간은 비즈니스에 있어서 자원이자 비용이기 때문에 이를 관리할 수 있다는 것은 결국 비용을 줄이고 수익을 높이는데 도움을 줄 수 있는 능력을 가졌다는 점이다. 그런 점에서 Big O는 경제적 관점에서도 가치가 있는 지식이다.

 

Scalability의 시간 복잡도에 영향을 미치는 요인은?

• Variables
• Data structure
• Function Call
• Allocations

 

참고할 만한 사이트

https://www.bigocheatsheet.com/