[알고리즘] 시작 - 시간 복잡도

알고리즘

• 시간 복잡도를 이용하면 작성한 코드가 시간이 대략 얼마나 걸릴지 예상 할 수 있다.
• 시간 복잡도는 소스를 보고 계산할 수도 있고, 소스를 작성하기 전에 먼저 계산해볼 수 있다.
• 문제를 풀기 전에 먼저 생각한 방법의 시간 복잡도를 계산해보고 이게 시간 안에 수행될 것 같은 경우에만 구현하는 것이 좋다.

 

문제의 크기

• 입력범의의 가장 큰 수를 시간복잡도에 대입하여 그 값에 따라 구현여부를 결정함

ex) 

1억 -> 1초

n <= 10 만

O(1) ->1-->0.00~1초 (아주 작은 초) 너무 빨라서 무시할수 있는 수

O(N) ->10만 ->0.001초

O(N^2) ->100억 --> 100초

•  시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때, 1억이 1초 정도이다
• 이 값은 대략적인 값으로, 실제로 구현해보면 1억을 조금 넘어도 1초이내에 수행이 가능하다

ex )
n<= 500
O(n^3) ->1.25 억 // 1초 이내의 수행 가능

 

 

• Big O Notation 에서 상수는 버린다 
  • O(3N^2 ) = O(N^2 )
• 두가지 항이 있을때, 변수가 같으면 큰것만 빼고 다 버린다.
  • O(N^2 + N) = O(N^2 )
• 두가지 항이 있는데 변수가 다르면 놔둔다.
  • O(N^2 + M) \

 

사용한 메모리

• 메모리 제한은 보통 넉넉하기 때문에 , 걱정할 필요가 없다
• 대략적으로 얼마나 공간을 사용할지 예상 할 수 있다
• 보통 가장 많은 공간을 사용하는 것은 보통 배열이다
• 불필요한 공간이 없다면, 대부분 메모리는 알아서 지켜진다