글 읽기 - 시간 복잡도 계산

richard0326 3년 전 0

일단 시간복잡도를 계산했을 경우, n이 최대 1000명, 득표수도 1000이기 때문에

다솜이가 0표이며 나머지가 999명이 모두 1000표를 갖고 있을 경우는 999번을 돌아야하고

while문의 반복 횟수는 최대 999이지만 1000으로 계산하고

sort는 merge sort임으로 nlogn이기 때문에

1000 x 1000 log(2) x 1000 = 300,000,000 이 됨으로 3초 걸리는 데. (1000 log(2) = 301.xxxx)

실제로는 2초 안에 들어온다.... 뭐지? ㅋㅋ

제가 계산한게 맞나여?

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int candidate[1001];

int main() {

	scanf("%d", &n);

	int target;
	scanf("%d", &target);
	for (int i = 1; i < n; i++)
		scanf("%d", &candidate[i]);

	sort(candidate + 1, candidate + n);

	int count = 0;
	while(target <= candidate[n-1])
	{
		candidate[n-1]--;
		target++;
		sort(candidate + 1, candidate + n);
		count++;
	}

	printf("%d\n", count);

	return 0;
}

djm03178 3년 전 1

1억은 1초가 아닙니다. 요즘 컴퓨터는 1초에 10억, 가벼운 연산은 20억도 돌립니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 복잡도 계산

richard0326 3년 전 0

djm03178 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말