Libraion's blog

[Help] Testcase for Prim N^2 much faster than Prim (N + M)log
By Libraion, history, 3 years ago, In English

I'm trying to generate a testcase so that Prim with complexity $$$O(N^2)$$$ is significantly faster than Prim with priority queue $$$O((N + M)log(N + M)$$$ (Here $$$N$$$ is number of vertices and $$$M$$$ is number of edges).

However as I generate with random weight of the edges the two algorithm runs with nearly the same amount of time (I generate with $$$N = 2500$$$ and $$$M = N * (N - 1) / 2$$$ (As polygon doesn't allow bigger constraint)).

I wonder if there is a way to construct such test (that for example, the priority queue contains many elements while running...).

Thanks.

  • Vote: I like it
  • +89
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you able to provide the source code of your implementations? I suspect that you did not implement the first version correctly.

→ Reply
»
3 years ago, # |
  Vote: I like it +89 Vote: I do not like it

Reading the input is slower than other standard operations. If the input size is $$$M$$$, you can assume that reading the input is $$$O(M \cdot \log M)$$$. With this assumption, you're trying to distinguish between two algorithms with same time complexity.

Try a compressed input like:

0110
1000
1001
0010
→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

pls let me get a new haircut

→ Reply
»
3 years ago, # |
  Vote: I like it +33 Vote: I do not like it

http://usaco.org/index.php?page=viewproblem2&cpid=946

This problem forced $$$\mathcal O(N^2)$$$ Prim's by setting $$$N \leq 7500$$$ and using an alternative scheme for generating the edge weights to get around input bottleneck. If you take this approach, make sure you pick a better edge weight function because this particular function allowed unintended $$$\mathcal O(1)$$$ solutions.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can drive vertexes into 2 groups, and have small weights inside each one, and big weights from one to another.

→ Reply