java - How large does a graph need to be to trigger the worst-case complexity of a Fibonacci heap? -


i've been trying trigger worst-case complexity of fibonacci heap using dijkstra's algorithm apparently no luck. have second implementation of dijkstra's using vanilla binary heap, , seems win. told conduct tests using larger datasets, have, shown (copy-pasted straight program):

running dijkstra's algorithm 3354 nodes , 8870 links... source node: time using binary heap = 2167698339 ns (2167.70 ms)

versus...

running dijkstra's algorithm 3354 nodes , 8870 links... source node: time using fibonacci heap = 11863138070 ns (11863.14 ms)

2 seconds, against ~12 seconds. quite difference alright.

now, have graph whopping 264,000 nodes , 733,000 edges. haven't had chance test yet, enough theoretical advantage of fibonacci heaps shine?

i hope don't need on million nodes. mean it's not biggest issue in world nice see difference in action once.

first of question's title not correct. size of input not affect worst case complexity. need size of graph asymptotic computational complexity of fibonacci heap makes constant factor. remember old o(n)? o(n) mean large enough datasets algorithm perform approximately k*n operations, k fixed number. k constant refering to. if have algorithm complexity o(n) , compexity o(n*log(n)), still not mean first 1 faster second one. imagine first 1 performs k1*n operations , second 1 performs k2n*log(n) operations. if k1 = k2 * 1000, fact first algortihm faster second 1 if n > 21000, quite large. important if have value first algorithm overtake second one.

depending on implementation of given datastructure, constant may vary , may need several times larger dataset make it. have seen results fibonacci heap got faster plain old binary heap @ 500 000 edges(and 5000 nodes) these particular implementation. in implemenation difference may show earlier, or later depending on how efficiently implemented both structures. if implemented data structures correct complexities, difference show n(but may happen no existing computer can handle graphs big).


Comments

Post a Comment

Popular posts from this blog

Why does Ruby on Rails generate add a blank line to the end of a file? -

running rails generate controller foo home results in: class foocontroller < application controller def home end end (there's nothing on line in actual file, blank line) is there purpose blank line? it's common use newline indicate end of line, last line. many editors (like vi, use) add in newline silently. consensus text files (especially in unix world) should end in newline, , there have been problems historically if wasn't present. why should text files end newline? the tool used count lines in file "wc" counts newlines in file, without trailing newline show 3 instead of 4. it improves readability of templates used in generator. consider: https://github.com/rails/rails/blob/master/railties/lib/rails/generators/rails/controller/templates/controller.rb to remove trailing newline, template have last line of: end<% end -%> instead of: end <% end -%> that seems less readable me. the discussion below refers
Read more

keyboard - Smiles and long press feature in Android -

i've created android keyboard. how add features inserting smilies, , using long keypresses display symbols? to create long-press behavior allows select several options pop-up menu, follow guide (specifically pop-up menu section): http://developer.android.com/guide/topics/ui/menus.html smileys (also known emoticons) combination of keys, understood programs , parsed same way. have do, when clicks smiley face on keyboard, simulate pressing of key combination matching emoticon. example, when clicks smiley, should simulate key presses ':' , ')' :). here's list of emoticons: http://en.wikipedia.org/wiki/list_of_emoticons
Read more

node.js - Bad Request - node js ajax post -

i'm using express 3.0 , node v0.11.0. have button submits form , i'm using ajax post data json object node server. client code is: $('#contact').submit(function(e) { console.log('submit called'); var formdata = json.stringify($('form').serializeobject()); console.log(formdata); $.ajax({ url: "http://localhost:3000/savedata/", type: "post", datatype: 'json', data: {objectdata: formdata}, contenttype: "application/json", complete: function() { console.log('process complete'); }, success: function(data) { console.log('process sucess'); }, error: function() { console.log('process error'); }, }); return false; }); then on server: var express = require('express'); var app = express(); app.set('views', __dirname + '/views'); app.set('view engine', 'jade'); app.use(express.bodyparser());
Read more