시간 복잡도 | DSA 001

코드 성능을 계산하는 방법

접근법 1: 시간 기반 접근법

calculateTime()
function fancyName(){
   do something
}
calculateTimeDifference()

코드를 판단하는 이 접근 방식에서는 코드 덩어리를 실행하기 전에 초기 시간이 걸리고 해당 코드를 실행한 후 마지막 시간이 걸립니다. 그런 다음 초기 시간에서 최종 시간을 빼면 코드 처리에 필요한 시간을 알 수 있습니다.

코드 성능을 계산하는 이 방법은 평균으로 평가되지만 여전히 이 접근 방식은 코드를 판단하는 데 많이 사용됩니다.

접근법 1의 문제점:

기계 기반: 프로세서마다 다름

처리 기반: PC의 처리 능력에 따라 다름

접근 2:

코드에서 작업 수를 계산합니다. 기술적으로 이것은 문자 그대로 코드의 작업 수를 세는 것을 의미합니다.

아래 코드에서 카운트 연산a = a + 1
한 가지 수술이 있다고 하면 친구가 틀렸습니다. 실제로 2개의 연산자가 있습니다: "="및 "+"

이제 이 코드에서 작업을 계산합니다.

sum = 0
winner = 1
for (i = 1; i < n; i++){
  sum = sum+1
}

여러 연산자가 있음을 자세히 살펴보십시오. 총 3개의 "="s, 1개의 "<"가 있고, i++에는 실제로 i의 값을 증가시키는 역할을 하는 2개의 연산자가 있습니다. i++는 i = i+1로 쓸 수 있습니다. i++ 2명의 운영자가 있습니다. 그런 다음 루프 내부에는 "="및 "+"라는 두 개의 연산자가 있습니다.

그러나 이 코드에서 sum = 0 , winner = 1 , i=1 를 제외한 다른 모든 연산자는 변수 n 에 종속됩니다. 따라서 3개의 상수 연산자와 n 값에 따라 달라지는 5개의 연산자가 있습니다. 따라서 3+5n 연산자가 있습니다.

빅 오

여러 연산자로 코드를 측정하는 전체 방법을 Big O라고 합니다.

코드 1

sum = 0
i = 0
while (i < n):
    sum += i
    i += 1
print(sum)

이 주어진 코드에는 5n+2개의 연산자가 있습니다.

이제 코드의 복잡성을 살펴보겠습니다. 코드의 복잡성을 측정하려면 상수를 무시해야 합니다.

따라서 O(n) [n의 O라고 함]은 복잡성입니다.

코드 2

for (------):
  ---------
  ---------
for (------):
  ---------
  ---------

위 코드의 복잡도가 2O(n)이라고 생각할 수 있으며 완전히 맞습니다. 그러나 상수는 무시해야 하므로 복잡도는 O(n)이 됩니다.

코드 3

for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    sum+=j
  }
}

위의 코드에서 O(n)은 다른 O(n) 안에 있습니다. 따라서 코드의 복잡도는 O(n^2)가 됩니다. 중첩 루프가 N이 아닌 상수에서 실행되는 경우 복잡성은 O(n^2)가 아닙니다.

복잡성 표기법

코드 복잡성
표기법
메모


O(10), O(1000) O(k), 3O(k) kO(k)
오(1)
"k"는 상수입니다.

O(3n), O(4n+100000)
에)
상수는 무시됩니다.

O(3n^2), O(4n^2+100000)
오(n^2)
상수는 무시됩니다.

O(3n^2), O(4n^2 + 3n + 4)
오(n^2)
n의 값이 증가함에 따라 n^2의 값이 n의 값보다 훨씬 높아지므로 n은 무시할 수 있습니다. 삼차 방정식의 경우 복잡도는 O(n^3)이 됩니다.




이 그래프는 입력이 증가함에 따라 코드가 복잡해지는 시간을 보여줍니다.