数据结构的时间复杂程度分析
原标题：Time complexity analysis of data structures
I got a bit confused about analzsis of data structure basic operation like inserting or deleting.
when I am asked about creating an data structure that support deleting operation, or inserting in O(1), (or any big O):
For deleting do I need take in account the searching of this element or only the deleting operation it self, for example changing the pointers?
For the inserting do I need to take in account the searching of the index/point where I need to place the element
I look a bit in the Internet but I got diffrenet time complexity for the basic data structure I learnedd, for example in Array, I saw both O(1) and O(N)
Thanks
问题回答
To answer both of your questions, what is included in the time complexity of an operation depends on how much extra work you needed to do for that specific operation.
For instance, given an array and an element, delete would take O(n) time and would include searching the element in the array. However, if that same array is assumed to have properties of a stack, the time complexity of delete operation would become O(1) since we already know the element s position.
An example with the insert operation would be inserting an element to the end of a linked list. When implemented without a tail pointer, time is O(n), but with a tail pointer it is O(1).
Hence, analysing time complexities is less about operations having rigid time complexities as such and more about its implementation details.
Hope this clarifies things. Feel free to discuss any particular eg. you found confusing in the comments :)
Normally, the question "how much does it cost to insert?" or "how much does it cost to delete?" is asking about the operations:
structure.insert(value)
structure.delete(value)
so that the cost of finding where value goes is part of the cost.
But some languages like Java have a list iterator, where you can iterate over a list and say "add an element at the current position" or "delete the current element". In that case, you already know where you are.
The default answers are "yes, you do need to take the extra work into account".
To understand the questions, let s see why. Why do we ask questions about complexity of operations in a data structure? Most of the time, we want to use the data structure. Like a black box. The typical usage pattern is:
the data structure is ready for any use, no extra info is present
we want to do operation X, for example, insert an element
the data structure is again ready for any use, no extra info is stored
We want to estimate the time it typically takes to arrive from the former state to the latter. So, any and all operations in between should be accounted for.
That said, sometimes the question "what time does it take to do X not accounting for some preparation step Y" also makes sense.
For example, we can find the convex hull of n points on a plane in O(n), provided that the points are already sorted in some convenient way. The same task would take O(n log n) for unsorted input. Indeed there are cases where the input is already sorted, so both answers make sense in different contexts.
For another example, in a balanced binary search tree, we can find a specific element in O(log n). However, iterating over all n elements takes only O(n) time, instead of O(n log n). So, we say that iterating over an element in this scenario takes O(1) amortized time.
相关问题
How to add/merge several Big O s into one
If I have an algorithm which is comprised of (let s say) three sub-algorithms, all with different O() characteristics, e.g.:
algorithm A: O(n)
algorithm B: O(log(n))
algorithm C: O(n log(n))
How do ...
Finding the spin of a sphere given X, Y, and Z vectors relative to sphere
I m using Electro in Lua for some 3D simulations, and I m running in to something of a mathematical/algorithmic/physics snag.
I m trying to figure out how I would find the "spin" of a sphere of a ...
Grokking Timsort
There s a (relatively) new sort on the block called Timsort. It s been used as Python s list.sort, and is now going to be the new Array.sort in Java 7.
There s some documentation and a tiny Wikipedia ...
Manually implementing high performance algorithms in .NET
As a learning experience I recently tried implementing Quicksort with 3 way partitioning in C#.
Apart from needing to add an extra range check on the left/right variables before the recursive call, ...
Print possible strings created from a Number
Given a 10 digit Telephone Number, we have to print all possible strings created from that. The mapping of the numbers is the one as exactly on a phone s keypad.
i.e. for 1,0-> No Letter
for 2->...
Enumerating All Minimal Directed Cycles Of A Directed Graph
I have a directed graph and my problem is to enumerate all the minimal (cycles that cannot be constructed as the union of other cycles) directed cycles of this graph. This is different from what the ...
Find number of permutations of a given sequence of integers which yield the same binary search tree
Given an array of integers arr = [5, 6, 1]. When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child.
Now if our input is ...
Quick padding of a string in Delphi
I was trying to speed up a certain routine in an application, and my profiler, AQTime, identified one method in particular as a bottleneck. The method has been with us for years, and is part of a "...
