글 읽기 - 제 코드의 시간복잡도를 계산해주실 수 있으신가요??

stiti 6년 전 0

1. visited를 이용해서 방문한 노드를 체크하고

2. 체크된 노드들 중에서 가장 작은 값을 갖는 엣지를 연결하는

방식으로 해결하였습니다.

시간은 다른분들 코드보다 10배정도 더 걸리는 것 같은데요.

제 코드의 시간복잡도를 계산할 수가 없어서 질문드립니다.

제가 시간복잡도 이런걸 잘 모릅니다...ㅠㅠ

가장 바깥쪽의 while(1)이 vertex의 개수 -1 만큼 돌아가므로

while(!Q.empty())에서 Queue에 들어있는 Vertex들의 Edge를 조사하므로

한개의 Vertex에 연결된 Edge수의 평균은 E/V 이고 계산되는 Vertex의 평균은 V/2 이므로

(E/V) * (V/2) = E/2

V * (E/2) = 세타(VE)

이런식으로 계산하면 되는건가요..?

알려주시면 감사드리겠습니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int result = 0;
int n, m;
bool visited[1001];
const int INF = 987654321;
vector<pair<int, int>> graph[1001];
int arr[1001][1001];
void go()
{
	queue<int> Q;
	visited[1] = true;
	while (1)
	{
		for (int i = 1; i <= n; i++)
		{
			if (visited[i])
				Q.push(i);
		}
		int node;
		int val = INF;
		while (!Q.empty())
		{
			int temp = Q.front();
			Q.pop();
			for (int d = 0; d < graph[temp].size(); d++)
			{
				int next = graph[temp][d].first;
				int weight = graph[temp][d].second;
				if (visited[next])
					continue;
				if (weight < val)
				{
					val = weight;
					node = next;
				}
			}
		}
		visited[node] = true;
		result += val;
		bool bit = false;
		for (int i = 1; i <= n; i++)
		{
			if (!visited[i])
				bit = true;
		}
		if (!bit)
		{
			cout << result << endl;
			return;
		}
	}
}
int main()
{
	scanf("%d", &n);
	scanf("%d", &m);
	int a, b, c;
	for (int i = 1; i <= m; i++)
	{
		scanf("%d", &a);
		scanf("%d", &b);
		scanf("%d", &c);
		graph[a].push_back(make_pair(b, c));
		graph[b].push_back(make_pair(a, c));
	}
	go();
	return 0;
}