47-算法解析

2.7.6　算法解析

（1）时间复杂度：在Prim（int n，int u₀，int c[N][N]）算法中，一共有4个for语句，第①个for语句的执行次数为n，第②个for语句里面嵌套了两个for语句③、④，它们的执行次数均为n，对算法的运行时间贡献最大。当外层循环标号为1时，③、④语句在内层循环的控制下均执行n次，外层循环②从1～n。因此，该语句的执行次数为n*n=n²，算法的时间复杂度为O(n²)。

（2）空间复杂度：算法所需要的辅助空间包含i、j、lowcost和closest，则算法的空间复杂度是O(n)。