알고리즘/기법,기초
-
시간복잡도알고리즘/기법,기초 2022. 7. 31. 09:52
시간복잡도는 프로그램의 수행시간을 다항식으로 나타내는 것이다. 시간복잡도는 시간제한이 있는 OJ사이트나 코딩 테스트,대회 등에서 중요한 요소이다. 하지만 대부분의 사람들은 시간복잡도를 그냥 대충 계산하는 경향이 있다.(사실 그래도 된다.) 그러나 필자는 깊이 있는 문제 풀이를 위해 시간복잡도가 굉장히 중요한 요소라 생각하기에 이에 대해 말해 보겠다. 1.시간복잡도 계산 그 프로그램에 있는 반복문의 반복 횟수라 봐도 문제가 없다. arr[1]과 같은 한 번에 접근 가능한 것을 O(1)의 시간복잡도를 가졌다 하고, 이는 그 프로그램의 시간복잡도에서 보통 생략된다. 예를 들어보자. n=int(input()) for i in range(n): print(i) 다음의 코드는 i가 0부터 n까지 1씩 증가하는 코드..