Surely you could implement this via a sorting algorithm? If you can prove the distance function is a metric and both lists contains elements from the same space under that metric, isn’t the answer to sort both?
unless the problem space includes all possible functions f , function f must itself have a complexity of at least n to use every number from both lists , else we can ignore some elements of either of the lists , therby lowering the complexity below O(n!²)
if the problem space does include all possible functions f , I feel like it will still be faster complexity wise to find what elements the function is dependant on than to assume it depends on every element , therefore either the problem cannot be solved in O(n!²) or it can be solved quicker
Problem: Given two list of length n, find what elements the two list have in common.
(we assume that there are not duplicates within a single list)
Naive solution: For each element in the first list, check if it appears in the second.
Bogo solution: For each permutation of the first list and for each permutation of the second list, check if the first item in each list is the same. If so, report in the output (and make sure to only report it once).
lol, you'd really have to go out of your way in this scenario. First implement a way to get every single permutation of a list, then to ahead with the asinine solution. 😆 But yes, nice one! Your imagination is impressive.
if I'm not mistaken , a example of a problem where O(n!²) is the optimal complexity is :
There are n traveling salespeople and n towns . find the path for each salesperson with each salesperson starting out in a unique town , such that the sum d₁ + 2 d₂ + ... + n dₙ is minimised, where n is a positive natural number , dᵢ is the distance traveled by salesperson i and i is any natural number in the range 1 to n inclusive .
pre post edit, I realized you can implement a solution in 2(n!) :(
After all these years I still don’t know how to look at what I’ve coded and tell you a big O math formula for its efficiency.
I don’t even know the words. Like is quadratic worse than polynomial? Or are those two words not legit?
However, I have seen janky performance, used performance tools to examine the problem and then improved things.
I would like to be able to glance at some code and truthfully and accurately and correctly say, “Oh that’s in factorial time,” but it’s just never come up in the blue-collar coding I do, and I can’t afford to spend time on stuff that isn’t necessary.
A quadratic function is just one possible polynomial. They're also not really related to big-O complexity, where you mostly just care about what the highest exponent is: O(n^2) vs O(n^3).
For most short programs it's fairly easy to determine the complexity. Just count how many nested loops you have. If there's no loops, it's probably O(1) unless you're calling other functions that hide the complexity.
If there's one loop that runs N times, it's O(n), and if you have a nested loop, it's likely O(n^2).
You throw out any constant-time portion, so your function's actual runtime might be the polynomial: 5n^3 + 2n^2 + 6n + 20. But the big-O notation would simply be O(n^3) in that case.
I'm simplifying a little, but that's the overview. I think a lot of people just memorize that certain algorithms have a certain complexity, like binary search being O(log n) for example.
Time complexity is mostly useful in theoretical computer science. In practice it’s rare you need to accurately estimate time complexity. If it’s fast, then it’s fast. If it’s slow, then you should try to make it faster. Often it’s not about optimizing the time complexity to make the code faster.
All you really need to know is:
Array lookup: O(1)
Single for loop: O(n)
Double nested for loop: O(n^2)
Triple nested for loop: O(n^3)
Sorting: O(n log n)
There are exceptions, so don’t always follow these rules blindly.
It’s hard to just “accidentally” write code that’s O(n!), so don’t worry about it too much.
It has been a while since I have to deal with problem complexities in college, is there even class of problems that would require something like this, or is there a proven upper limit/can this be simplified? I don't think I've ever seen O(n!^k) class of problems.
Hmm, iirc non-deterministic turing machines should be able to solve most problems, but I'm not sure we ever talked about problems that are not NP. Are there such problems? And how is the problem class even called?
Oh, right, you also have EXP and NEXP. But that's the highest class on wiki, and I can't find if it's proven that it's enough for all problems. Is there a FACT and NFACT class?