[JavaScript] 알고리즘 공부기록 : 팩토리얼 / 법칙

function fact(n) {
  return n > 0 ? n * fact(n - 1) : 1;
}

console.log(fact(10));

 

 

 

계수법칙 / 합의법칙 / 다항법칙 / 곱의 법칙 / 전이법칙 

 

1. 계수법칙

(상수 k>0) f(n)이 O(g(n)) 이면 kf(n) 은 O(g(n)) 이다. 

gpt 설명 :: 

질문 :: 

(상수 k>0) f(n)이 O(g(n)) 이면 kf(n) 은 O(g(n)) 이다. 시간복잡도에서 나온것 중 하나인데 kf(n)이면 O(g(n*k)) 이렇게되어야할거같은데아님?

답 ::

계수법칙이란, 어떤 함수 f(n)f(n)f(n)가 O(g(n))O(g(n))O(g(n))라면 kf(n)kf(n)kf(n) (여기서 k>0k > 0k>0)도 O(g(n))O(g(n))O(g(n))에 속한다는 법칙입니다.

• 예를 들어, f(n)=3n2f(n) = 3n^2f(n)=3n2이고 g(n)=n2g(n) = n^2g(n)=n2라면,
  f(n)∈O(g(n))f(n) \in O(g(n))f(n)∈O(g(n))이므로 kf(n)=5×3n2=15n2kf(n) = 5 \times 3n^2 = 15n^2kf(n)=5×3n2=15n2도 O(n2)O(n^2)O(n2)에 속합니다.
• 왜 이런 일이 일어나나요?
  • 상수 kkk는 함수의 성장 속도를 바꾸지 않기 때문입니다. 시간복잡도는 함수가 nnn이 커질 때의 "성장 속도"에만 관심이 있기 때문에, 상수 계수 kkk는 결과적으로 무시됩니다.

왜 kf(n)kf(n)kf(n)가 O(g(n))O(g(n))O(g(n))이지 O(g(n⋅k))O(g(n \cdot k))O(g(n⋅k))가 아닌가?

1. kkk는 상수입니다. O(g(n))O(g(n))O(g(n)) 표기법에서는 상수 계수나 항을 무시합니다.
   따라서 g(n⋅k)g(n \cdot k)g(n⋅k)처럼 상수 kkk를 함수의 독립 변수에 곱할 필요가 없습니다.
2. 시간복잡도는 함수의 독립 변수 nnn이 무한히 커질 때를 다루기 때문에, 상수는 성장 속도에 영향을 주지 않습니다.

예시로 이해하기

f(n)=3n2f(n) = 3n^2f(n)=3n2, k=10k = 10k=10:

• g(n)=n2g(n) = n^2g(n)=n2라면,
  f(n)∈O(g(n))f(n) \in O(g(n))f(n)∈O(g(n))
  kf(n)=10⋅3n2=30n2kf(n) = 10 \cdot 3n^2 = 30n^2kf(n)=10⋅3n2=30n2 역시 O(n2)O(n^2)O(n2).

O(g(n⋅k))O(g(n \cdot k))O(g(n⋅k))로 처리하면:

• g(n⋅k)=(n⋅k)2=k2⋅n2g(n \cdot k) = (n \cdot k)^2 = k^2 \cdot n^2g(n⋅k)=(n⋅k)2=k2⋅n2상수 k2k^2k2가 포함되므로, 이는 시간복잡도 표기법의 의미와 맞지 않습니다.

=> 이해한 것 : 상수를 곱해도 시간복잡도에는 영향을 안미친다

 

2. 합의 법칙

f(n)이 O(h(n))이고, g(n)이 O(p(n))이라면 f(n)+g(n)은 O(h(n)) + p(n))이다. 

=> 이해한 것 : 함수 f(n)이 복잡도  O(h(n))를 가지고있고 

함수 g(n)이 복잡도 O(p(n))를 가지고 있다면

이 함수 두개를 실행시켰을 때의 복잡도는 이 둘을 더한 것과 같다 

=> gpt :

• 일반적으로, 합의 법칙은 **"가장 큰 성장을 가진 항"**에 따라 결정됩니다.
• 즉, O(h(n)+p(n))O(h(n) + p(n))O(h(n)+p(n))가 맞지만, 실제로는 둘 중 더 큰 성장 속도를 가진 함수가 최종 시간복잡도를 결정합니다.

 

 

3. 다항법칙

f(n)이 k차 다항식이면 f(n)은 O(n^k)다.

=> 이해한 것 : 함수 f(n)을 k번만큼 실행시키면 원래 f(n)이 가지고있던 시간 복잡도 O(n)의 k 번 만큼

시간 복잡도가 증가하는데 이걸 식으로 표현하면 O(n^k)로 표현할 수 있다 

=> gpt :

 

• 시간복잡도는 실행 횟수와는 무관합니다. 다항 법칙은 kkk번 실행하는 게 아니라, 함수의 형태 자체가 kkk차 다항식이라는 점에 초점이 있습니다.
• f(n)=aknk+ak−1nk−1+⋯+a1n+a0f(n) = a_k n^k + a_{k-1} n^{k-1} + \dots + a_1 n + a_0f(n)=ak​nk+ak−1​nk−1+⋯+a1​n+a0​ 같은 다항식이라면, n→∞n \to \inftyn→∞일 때 가장 높은 차수 항인 nkn^knk만 중요하기 때문에 O(nk)O(n^k)O(nk)로 표현됩니다.
• 예시:
  • f(n)=3n4+2n2+7f(n) = 3n^4 + 2n^2 + 7f(n)=3n4+2n2+7이라면 f(n)∈O(n4)f(n) \in O(n^4)f(n)∈O(n4).
    (가장 높은 차수인 n4n^4n4만 남김).
  • 결론:
    • 다항식에서 가장 높은 차수 항만이 시간복잡도를 결정하며, 실행 횟수와는 무관합니다.

 

 

4. 곱의 법칙

f(n)이 O(h(n))이고 g(n)이 O(p(n))이면 f(n)g(n)은 O(h(n)p(n)이다.

=> 이해한 것 : 각각의 시간복잡도를 가진 두 함수의 곱은 

각각의 시간복잡도를 곱한 것과 같다 

=> gpt :

두 함수의 시간복잡도를 곱할 경우, 그 곱은 두 시간복잡도의 곱으로 표현됩니다.

• f(n)=O(h(n))f(n) = O(h(n))f(n)=O(h(n)), g(n)=O(p(n))g(n) = O(p(n))g(n)=O(p(n))라면, f(n)⋅g(n)=O(h(n)⋅p(n))f(n) \cdot g(n) = O(h(n) \cdot p(n))f(n)⋅g(n)=O(h(n)⋅p(n)).

 

 

5. 전의법칙

f(n)이 O(g(n))이고 g(n)이 O(h(n))이면 f(n)은 O(h(n))이다.

=> 이해한 것 : 

function fact() {
 console.log('hello world!') // O(1)
}
function hello(){
  return fact() // O(1)
}
hello();

 

=> gpt :

전의 법칙은 시간복잡도의 "전달"을 설명하는 규칙입니다.

1. 어떤 함수 f(n)f(n)f(n)가 g(n)g(n)g(n)에 속하고,
2. 또 g(n)g(n)g(n)가 h(n)h(n)h(n)에 속하면,
3. 결국 f(n)f(n)f(n)도 h(n)h(n)h(n)에 속하게 된다는 뜻입니다.

 

 

• 2. 합의 법칙: 두 시간복잡도를 더한 후, 더 높은 차수의 함수가 전체 시간복잡도를 지배한다.
• 3. 다항 법칙: 다항식의 시간복잡도는 가장 높은 차수의 항에 의해 결정된다. 실행 횟수와는 무관.
• 4. 곱의 법칙: 두 함수의 시간복잡도를 곱하면, 각각의 시간복잡도를 곱한 것으로 표현된다.
• 5. 전의 법칙 :
  • 전의 법칙은 "점근적 상한 관계"가 계층적으로 연결될 때 최종 상한을 쉽게 추론하는 법칙입니다.
  • 한 함수가 두 단계 이상 상위 복잡도의 집합에 포함될 때 유용합니다.