Блог пользователя Libraion

Автор Libraion, история, 2 года назад, По-английски

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.

  • Проголосовать: нравится
  • +89
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +89 Проголосовать: не нравится

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
»
2 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

pls let me get a new haircut

»
2 года назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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