인프런 커뮤니티 질문&답변

안녕하세요 강사님, 강의 잘 듣고 있습니다.

조합을 구하는 함수의 시간복잡도에 대해 질문 드리고 싶습니다.

// Online C++ compiler to run C++ program online
#include <iostream>
#include <vector>
using namespace std;
int r=0;
vector<int> t;
int cnt=0;
int forcount=0;
void combi(int idx)
{
    if(t.size()==r)
    {
        cnt++;
        return;
    }
    for(int i=idx; i<=10; i++)
    {
        forcount++;
        t.push_back(i);
        func(i+1);
        t.pop_back();
    }
}

int main() {
    // Write C++ code here
    while(true){
        cnt=0;
        forcount=0;
        cin>>r;
        func(1);
        cout<<"cnt = "<<cnt<<"\n";
        cout<<"forcount = "<<forcount;
    }
    return 0;
}

조합 함수의 시간복잡도는 O(nCr), 위의 함수에서는 cnt의 값이라고 알고 있습니다.

그런데, 시간복잡도는 주어진 입력의 크기에 대한 연산의 총합이라고 알고 있습니다.

그러면, combi 함수의 for문 연산의 수인 forcount도 고려해야 하지 않나요?
왜? cnt만 고려해도 되는지 궁금합니다.