当前位置: 动力学知识库 > 问答 > 编程问答 >

math - differential equation VS Algorithms complexity

问题描述:

I don't know if it's the right place to ask because my question is about how to calculate a computer science algorithm complexity using differential equation growth and decay method.

The algorithm that I would like to prove is Binary search for a sorted array, which has a complexity of log2(n)

The algorithm says: if the target value are searching for is equal to the mid element, then return its index. If if it's less, then search on the left sub-array, if greater search on the right sub-array.

As you can see each time N(t): [number of nodes at time t] is being divided by half. Therefore, we can say that it takes O(log2(n)) to find an element.

Now using differential equation growth and decay method.

dN(t)/dt = N(t)/2

dN(t): How fast the number of elements is increasing or decreasing

dt: With respect to time

N(t): Number of elements at time t

The above equation says that the number of cells is being divided by 2 with time.

Solving the above equations gives us:

dN(t)/N(t) = dt/2

ln(N(t)) = t/2 + c

t = ln(N(t))*2 + d

Even though we got t = ln(N(t)) and not log2(N(t)), we can still say that it's logarithmic.

Unfortunately, the above method, even if it makes sense while approaching it to finding binary search complexity, turns out it does not work for all algorithms. Here's a counter example:

Searching an array linearly: O(n)

dN(t)/dt = N(t)

dN(t)/N(t) = dt

t = ln(N(t)) + d

So according to this method, the complexity of searching linearly takes O(ln(n)) which is NOT true of course.

This differential equation method is called growth and decay and it's very popluar. So I would like to know if this method could be applied in computer science algorithm like the one I picked, and if yes, what did I do wrong to get incorrect result for the linear search ? Thank you

网友答案:

The time an algorithm takes to execute is proportional to the number of steps covered(reduced here).

In your linear searching of the array, you have assumed that dN(t)/dt = N(t).

Incorrect Assumption :-

dN(t)/dt = N(t)
dN(t)/N(t) = dt
t = ln(N(t)) + d

Going as per your previous assumption, the binary-search is decreasing the factor by 1/2 terms(half-terms are directly reduced for traversal in each of the pass of array-traversal,thereby reducing the number of search terms by half). So, your point of dN(t)/dt=N(t)/2 was fine. But, when you are talking of searching an array linearly, obviously, you are accessing the element in one single pass and hence, your searching terms are decreasing in the order of one item in each of the passes. So, how come your assumption be true???

Correct Assumption :-

dN(t)/dt = 1
dN(t)/1 = dt
t = N(t) + d

I hope you got my point. The array elements are being accessed sequentially one pass(iteration) each. So, the array accessing is not changing in order of N(t), but in order of a constant 1. So, this N(T) order result!

分享给朋友:
您可能感兴趣的文章:
随机阅读: