[알고리즘] 시간복잡도

• 파이썬으로 PS를 공부하다 보면 시간초과(TLE)가 발생하는 일이 많이 발생한다. 항상 코드를 짜면서 '이게 적합할까?' 이런 생각들을 하게 된다.

1. 아래 링크는 파이썬 메소드별 시간복잡도가 정리되어있는 사이트이다.

   https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

2. 위의 사이트에서 참조할 수 없는 내용도 여럿 있었다. 시간복잡도를 체크할 수 있는 코드에 본인이 작성한 소스코드를 첨부해 확인할 수 있다.

import time
start_time = time.time()

#확인하고자 하는 소스코드 작성

end_time = time.time()
print("run time: ", end_time - start_time)

---

• 시간복잡도

• 백준이나 프로그래머스에서 여러 알고리즘 문제를 풀면서 시간 제한과 메모리 제한을 많이 봤다. 하지만 그 시간 제한과 메모리 제한을 어떻게 활용을 해서 알고리즘을 구성해야하는지 막막한 경우가 많았다. 여러 블로그와 유튜브를 직접 찾아보면서 어떤 식으로 구성을 해야할지 찾아보고 공부했다.
• 예시를 들어 이해해보자. 우리가 일반적으로 사용하는 이중 for문의 시간 복잡도는 O(N^2)이라고 알고 있다. 그런데 이걸 시간 제한으로 나온 초로 계산을 어떻게 할까?
• 결론부터 말하면 N으로 구성된 O()를 계산했을 때의 값이 1억 정도라면 1초 정도의 시간이 걸린다고 할 수 있다.

EX. N의 최댓값이 10만이라고 하고 문제에서 주어진다면 다음의 시간 복잡도를 어떻게 계산해야할까?

• O(N)의 시간 복잡도의 경우 O(100,000)이므로 1/1000초 정도가 걸린다고 예상할 수 있다.
• O(N^2)의 시간 복잡도의 경우 O(100,000) × O(100,000) = O(10,000,000,000)이므로 100초 정도가 걸린다고 예상할 수 있다.