Home >Common Problem >data structure time complexity

data structure time complexity

王林
王林Original
2019-10-30 16:07:388797browse

data structure time complexity

What is time complexity?

A certain function in the algorithm has n basic operations repeated, represented by T(n). Now there is an auxiliary function f(n), so that when n approaches infinity, T If the limit value of (n)/f(n) is a constant that is not equal to zero, then f(n) is said to be a function of the same order of magnitude as T(n), recorded as T(n)=O(f(n)), and is called O (f(n)) is the asymptotic time complexity of the algorithm, referred to as time complexity.

In layman terms, the so-called time complexity is to find a function f(n) of the same curve type to represent the trend of this algorithm as n continues to increase. When the input quantity n gradually increases, the limit case of time complexity is called the "asymptotic time complexity" of the algorithm.

Method for calculating time complexity:

1. Use constant 1 to replace all addition constants in the running time

2. Modification In the final number of runs function, only the highest order term

3 is retained, and the coefficients of the highest order term

are removed and arranged in increasing order of magnitude. Common time complexities are:

data structure time complexity

The above is the detailed content of data structure time complexity. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn