minimum spanning tree lua HPPL
|
11-02-2021, 11:57 AM
Post: #13
|
|||
|
|||
RE: minimum spanning tree lua HPPL
Version 3 assumed all edges vaild, unless specified otherwise.
I think the speed is due to not spend time to validate edges. By shuffling mapped indexes, it keep the points to examine low. Points to examine reduced to about 1/3 (and, no code to validate vertices) Note: test for member in list has O(n) --- Points examined, for oringinal Lua code, n = total points, k = vertices examined sum(n*k, k=1..n-1) = n * n*(n-1)/2 = n^3/2 - n^2/2 Points examined, with shuffled indexes, splitting off vertices and non-vertices. sum((n-k)*k, k=1..n-1) = sum((n-1)*k - k*(k-1), k=1..n-1) // see Funny Factorials and Slick Sums = (n-1) * n*(n-1)/2 - n*(n-1)*(n-2)/3 = n*(n-1)*(n+1)/6 = n^3/6 - n/6 |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)