diff options
| author | cathook <b01902109@csie.ntu.edu.tw> | 2014-04-23 00:22:20 +0800 |
|---|---|---|
| committer | cathook <b01902109@csie.ntu.edu.tw> | 2014-04-23 00:22:20 +0800 |
| commit | 4867c9321df88bea09dc026cddeb33126c14dc36 (patch) | |
| tree | d8ab3ba3e8b3e0746e62ead4bdcab23903f4fc75 | |
| parent | 38b23620954f142ccf6653a58c47ff04d516be9c (diff) | |
| download | meow-4867c9321df88bea09dc026cddeb33126c14dc36.tar meow-4867c9321df88bea09dc026cddeb33126c14dc36.tar.gz meow-4867c9321df88bea09dc026cddeb33126c14dc36.tar.bz2 meow-4867c9321df88bea09dc026cddeb33126c14dc36.tar.lz meow-4867c9321df88bea09dc026cddeb33126c14dc36.tar.xz meow-4867c9321df88bea09dc026cddeb33126c14dc36.tar.zst meow-4867c9321df88bea09dc026cddeb33126c14dc36.zip | |
zzz
| -rw-r--r-- | README.asciidoc | 23 | ||||
| -rw-r--r-- | README.html | 50 |
2 files changed, 70 insertions, 3 deletions
diff --git a/README.asciidoc b/README.asciidoc index bdaaeee..2c48307 100644 --- a/README.asciidoc +++ b/README.asciidoc @@ -328,7 +328,9 @@ bool `cmp`)|Vectors [NOTE] ======================================== -* 實測結果發覺比 `KD_Tree` 有效率多了... +* 實測結果發覺, 維度小的時候, 比起中規中矩的 `KD_Tree`, `VP_Tree` 有 +'randomp' 於其中, 因此時間複雜度只是期望值 'O(logN)' 但是測資大到 +一定程度, `KD_Tree` 效率會一整個大幅掉下, 但 `VP_Tree` 幾乎不受影響 * 'TODO' `insert()`, `erase()` 算是未完成功能 ======================================== @@ -545,6 +547,25 @@ Value const& `delta`) == Test +=== ACM 相關題目 +[options="header",width="70%",cols="3<s,3<,4^,1^,1<,2^m",grid="rows"] +|======================================================================= +| Name | Problem | Link | Status | Time | source +| KD_Tree | 'Retrenchment' | +http://acm.csie.org/ntujudge/problem.php?id=1971[NTU-OJ] +https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4052[ACM-ICPC Live] +| Accept | 0.083 | http://codepad.org/U85ruse5[codepad] + + +| VP_Tree | 'Retrenchment' | +http://acm.csie.org/ntujudge/problem.php?id=1971[NTU-OJ] +https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4052[ACM-ICPC Live] +| Accept | 0.516 | http://codepad.org/03dW6ZHV[codepad] + + +|======================================================================= + + == Bug Report / Contact diff --git a/README.html b/README.html index c002ad7..7e21096 100644 --- a/README.html +++ b/README.html @@ -1651,7 +1651,9 @@ bool <span class="monospaced">cmp</span>)</p></td> <div class="ulist"><ul>
<li>
<p>
-實測結果發覺比 <span class="monospaced">KD_Tree</span> 有效率多了…
+實測結果發覺, 維度小的時候, 比起中規中矩的 <span class="monospaced">KD_Tree</span>, <span class="monospaced">VP_Tree</span> 有
+<em>randomp</em> 於其中, 因此時間複雜度只是期望值 <em>O(logN)</em> 但是測資大到
+一定程度, <span class="monospaced">KD_Tree</span> 效率會一整個大幅掉下, 但 <span class="monospaced">VP_Tree</span> 幾乎不受影響
</p>
</li>
<li>
@@ -2400,6 +2402,50 @@ Value const& <span class="monospaced">delta</span>)</p></td> <div class="sect1">
<h2 id="_test">Test</h2>
<div class="sectionbody">
+<div class="sect2">
+<h3 id="_acm_相關題目">ACM 相關題目</h3>
+<table class="tableblock frame-all grid-rows"
+style="
+width:70%;
+">
+<col style="width:21%;">
+<col style="width:21%;">
+<col style="width:28%;">
+<col style="width:7%;">
+<col style="width:7%;">
+<col style="width:14%;">
+<thead>
+<tr>
+<th class="tableblock halign-left valign-top" > Name </th>
+<th class="tableblock halign-left valign-top" > Problem </th>
+<th class="tableblock halign-center valign-top" > Link </th>
+<th class="tableblock halign-center valign-top" > Status </th>
+<th class="tableblock halign-left valign-top" > Time </th>
+<th class="tableblock halign-center valign-top" > source</th>
+</tr>
+</thead>
+<tbody>
+<tr>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>KD_Tree</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><em>Retrenchment</em></p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock"><a href="http://acm.csie.org/ntujudge/problem.php?id=1971">NTU-OJ</a>
+<a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4052">ACM-ICPC Live</a></p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">Accept</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">0.083</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock monospaced"><a href="http://codepad.org/U85ruse5">codepad</a></p></td>
+</tr>
+<tr>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><strong>VP_Tree</strong></p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock"><em>Retrenchment</em></p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock"><a href="http://acm.csie.org/ntujudge/problem.php?id=1971">NTU-OJ</a>
+<a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4052">ACM-ICPC Live</a></p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock">Accept</p></td>
+<td class="tableblock halign-left valign-top" ><p class="tableblock">0.516</p></td>
+<td class="tableblock halign-center valign-top" ><p class="tableblock monospaced"><a href="http://codepad.org/03dW6ZHV">codepad</a></p></td>
+</tr>
+</tbody>
+</table>
+</div>
</div>
</div>
<div class="sect1">
@@ -2418,7 +2464,7 @@ E-Mail: cat.hook31894 ~在~ gmail.com <div id="footnotes"><hr></div>
<div id="footer">
<div id="footer-text">
-Last updated 2014-04-22 21:35:29 CST
+Last updated 2014-04-23 00:16:52 CST
</div>
</div>
</body>
|