Prim算法首先将所有的顶点插入到优先队列（二叉堆实现）中，时间开销为O(V log V)。然后decreaseKey操作将需要O(log q)的时间，q是优先队列中顶点的数目，q将会小于|V|。这个操作最多需要执行2*|E|次，在这种情况下，每一个顶点都会从优先队列中删除，图中的每一条边都会被访问两次。因此总性能是O((V+2*E)*log n)或者O((V+E)*log V)。