Am 06.06.2012 09:57, schrieb Invisible:
>>>> Union-find structures I assume?
>>>
>>> Actually, something much more complicated than that.
>>
>> Intersting, what was it, I'm curious? The only other algorithm with that
>> complexity I can think of off the top of my head is an MST algorithm.
>
> An optimisation algorithm for logic programming.
>
>> In that case, however, you may be further interested to know that the
>> standard union-find algorithm also has inverse Acermann complexity. Thus
>> there's an even simpler example of something with that "odd" complexity.
>
> That's really odd. The Ackermann function is an ad hoc function with
> arbitrarily-chosen coefficients which was thrown together to prove a
> point. Why it should /ever/ occur in real life is beyond me...


function" (which is probably the case), then I see nothing 
"arbitrarily-chosen" in its recursive definition.

Maybe the Ackermann function you know is a different one? According to 
Wikipedia, "'the Ackermann function' may refer to any of numerous 
variants of the original function", modified "to suit various purposes".

Post a reply to this message