Created
December 23, 2018 14:59
-
-
Save hdf/17deb800a28046d09341f81f78426d58 to your computer and use it in GitHub Desktop.
Based on the array in question, and the counter value (you have to put the code for that in the function in question yourself), this function will tell us the time complexity of the function.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function BigO(arr, arr3) { // Second array is optional | |
this.accumulator = 0; // Can be set here, or when calling ClosestMatch | |
/* function factorial(n, i) { | |
if (n > 171) // Overflow prevention | |
return Infinity; | |
if (typeof i == 'undefined') | |
i = 1; | |
if (n < i) | |
return 1; | |
if (n === i) | |
return n | |
let half = (n + i) >> 1; // divide (n + 1) by 2 and truncate to integer | |
return factorial(half, i) * factorial(n, half + 1); | |
}*/ | |
function factorial(n) { // Why not in standard Math object? | |
if (n > 171) // Overflow prevention | |
return Infinity; | |
let out = 1; | |
for (let i = 2; i <= n; i++) | |
out = out * i; | |
return out; | |
} | |
var Orders = [ | |
["O(1)", "constant"], | |
["O(log log n)", "double logarithmic", n => Math.log2(Math.log2(n))], | |
["O(log n)", "logarithmic", n => Math.log2(n)], | |
["O(n)", "linear", n => n], | |
["O(n log n) = O(log n!)", "linearithmic, loglinear, or quasilinear", n => n * Math.log2(n)], | |
["O(n^c) 0<c<1", "fractional power", (n, c) => Math.pow(n, c), c => c > 0 && c < 1], | |
["O(n^2)", "quadratic", n => n * n], | |
["O(2^n)", "exponential", n => Math.pow(2, n)], | |
["O((log n)^c) c>0", "polylogarithmic", (n, c) => Math.pow(Math.log2(n), c), c => c > 0], | |
["O(n^c)", "polynomial or algebraic", (n, c) => Math.pow(n, c), c => c != 2], | |
["O(c^n) c>1", "exponential", (n, c) => Math.pow(c, n), c => c > 1 && c != 2], | |
["O(n!)", "factorial", n => factorial(n)] | |
]; | |
this.ClosestMatch = (arr2, acc) => { | |
let n = arr.length; | |
if (typeof acc != 'number') // All parameters are optional | |
acc = this.accumulator; | |
if (typeof arr2 == 'number') // May be, that we get accumulator instead of a second array | |
acc = arr2; | |
if (typeof arr3 == 'object' && typeof arr2 != 'object') // Second array can be set here, in ClosestMatch, or at instantiation | |
arr2 = arr3; | |
let c = (typeof arr2 == 'object') ? arr2.length : undefined; | |
let min = acc - 1, i = 1, l = Orders.length, min_loc = 0; | |
while (i < l) { | |
if (Orders[i].length > 3 && (typeof c == 'undefined' || !Orders[i][3](c))) { // We skip if not applicable | |
i++; | |
continue; | |
} | |
let f = Orders[i][2](n, c); | |
//let d = Math.abs(acc - f); | |
let d = (f > acc) ? f - acc : acc - f; | |
//console.log('[' + i + '/' + (l - 1) + ']', Orders[i][0], f, 'diff:', d); | |
if (d < min) { | |
min = d; | |
min_loc = i; | |
} | |
i++; // Without c, we could just break here, but depending on the value of c, the order of Orders may vary, so we need to go through the whole list | |
} | |
return Orders[min_loc].slice(0, 2).concat(min); | |
} | |
} | |
var O = new BigO(new Array(10)); | |
console.log(O.ClosestMatch(3628800)); | |
console.log(O.ClosestMatch(new Array(5), 10000000)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment