시간 복잡도

시간 복잡도는 프로그래밍 알고리즘의 중요한 부분입니다. 시간 복잡도를 사용하여 코드를 실행하는 데 필요한 시간을 추정할 수 있습니다. 일반적으로 시간복잡도를 나타내기 위해 3개의 기호가 사용됩니다. 그들은 빅오 표기법, 오메가 및 세타입니다. omega는 최상의 시나리오를 나타내고 theta는 평균 시나리오를 나타내고 big O 표기법은 최악의 시나리오를 나타냅니다. 대부분 시간 복잡도를 분석하는 동안 최악의 시나리오를 계산합니다. 그래서 빅오 표기법을 사용합니다. O(1), O(n), O(n^2), O(logn), O(nlogn) 등과 같은 시간 복잡도에 대한 몇 가지 표기법이 있습니다.

먼저 O(1)에 대해 알아보겠습니다. 이것은 실제로 우리 코드가 일정한 시간 동안 실행된다는 것을 의미합니다. 예를 들어 x = 9 와 같은 파이썬 코드를 작성할 수 있습니다. 이 코드 줄은 시간 복잡도가 O(1)로 일정합니다. 마찬가지로 코드를 작성하면

x = 9
y = 5

여기서 시간 복잡도는 어떻게 될까요? 이 코드에서 각 줄의 시간 복잡도는 O(1)입니다. 이 Python 코드의 각 줄의 시간 복잡도는 O(1)이므로 코드의 시간 복잡도는 O(1+1)입니다. (2)? 아니요, O(2)도 상수 시간이고 O(1)이 상수 시간을 나타내는 데 사용되기 때문에 여전히 O(1)입니다.

하지만 코드에 루프가 있으면 어떻게 될까요? 이를 위한 코드를 작성해 봅시다.

for i in range(10):
   print(i)

여기서 print 문은 O(1)의 시간 복잡도를 가집니다. 이 for 루프에서 print 문은 10번 실행되므로 루프가 10번 실행되므로 시간 복잡도는 O(10)이 됩니다. 그러나 루프가 n번 실행되면 어떻게 될까요? 그러면 시간 복잡도는 O(n)이 됩니다. 따라서 단일 루프의 경우 시간 복잡도는 O(n)입니다. 하지만 우리 코드에 2개의 루프가 있다면 어떨까요? 예를 들어:

for i in range(n):
  print(i)
for j in range(n):
  print(j)

여기서 시간 복잡도는 O(n+n) 즉 O(2n)입니다. 그러나 시간 복잡성을 작성하기 위해 우리는 상수를 무시합니다. 따라서 이 코드의 시간복잡도는 O(n)이 됩니다.

게다가, 우리는 O(n^2)라는 또 다른 시간 복잡도에 대해 이야기할 것입니다. 이 시간 복잡도는 중첩 루프에 대한 것입니다. 예를 들어:

for i in range(n):
  for j in range(n):
     print(i,j)

이 코드에는 중첩된 for 루프가 있으므로 코드는 O(n*n)번, 즉 O(n^2)번 실행됩니다. 이 경우에도 상수가 있으면 제거합니다. 이 코드의 시간 복잡도는 어떻게 됩니까?

for i in range(2n):
   for j in range(n):
       print(i,j)
for a in range(n):
  print(a)

이 코드에서 시간 복잡도는 O(2*(n^2)+n)일까요? 아니요, 여전히 코드의 시간 복잡도는 O(n^2)입니다. 그 이유는 빅오 표기법을 작성할 때 상수를 무시하기 때문입니다. 따라서 2는 big O 표기법으로 작성되지 않습니다. 그러나 시간 복잡도가 O(n)이 아닌 이유는 또 다른 질문입니다. 그 이유는 우리가 Big O 표기법에서 얻는 방정식의 가장 높은 거듭제곱을 취하기 때문입니다. 이것이 코드의 시간 복잡도가 O(n^2)인 이유입니다.