Data item: the smallest unit that constitutes a data element

Abstract data organization and operations related to it

Advantages: Random access can be achieved and takes up less storage space

Disadvantages: Only an adjacent block of storage units can be used, which may cause external fragmentation

Advantages: No fragmentation, full use of all storage units

Disadvantages: Pointers take up extra space and can only achieve sequential access.

Advantages: fast retrieval speed

Disadvantages: The index table takes up extra space; when adding or deleting data, the index table needs to be modified, which is more time-consuming.

Advantages: retrieval, adding and deleting nodes are all very fast

Disadvantages: If the hash function is not good, element storage unit conflicts may occur, causing additional time and space overhead.

For the logical structure, point out the function of the operation

For the storage structure, point out the specific operation steps of the operation

T(n)——The sum of the frequencies of all statements in the algorithm

f(n)——the frequency of basic operations in the algorithm

O——Order of magnitude

Formula definition: If T(n) and f(n) are two functions defined on the set of positive integers, then there are positive constants C and n0, such that when n>=n0, both satisfy 0=<T(n) =<Cf(n)

Worst time complexity

average time complexity

best time complexity

a. Addition rule

b. multiplication rule