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

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

다름이 아니라 제가 짠 코드로도 100점이 나오긴 하는데, 강사님이 설명해주신 코드와는 방식이 조금 달라 해당 코드의 시간 복잡도에 대해 여쭤보고자 질문 드립니다.

 

#include <iostream>
using namespace std;

int main()
{
	int count = 0;
	int max = 0;
	int input;

	cin >> input;

	for (int i = 1; i <= input; i++)
	{
		count = 0;
		max = i;
		for (int j = 1; j <= max; j++)
		{
			if (i % j == 0)
			{
				if ((i / j) != j)
					count++;

				max = (i / j) - 1;
				count++;
			}
		}
		cout << count << ' ';
	}
	cout << endl;
}

 

시간 복잡도 O(n^2)의 코드와 유사한데, for문을 한 번 계산할 때마다 max 값을 줄여 약수의 절반을 찾아내면 다음 for문으로 넘어가는 방식의 코드예요.

실제로 for문이 도는 건 원래의 값보다 훨씬 적긴 한데 O(logn * n)보다는 오래 걸리는 것처럼 보여서... 이 코드의 시간 복잡도도 O(n^2)이 맞나요?