Shulou(Shulou.com)06/03 Report--

In this issue, the editor will bring you about how to use C++ for algorithm analysis. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

Time complexity

O (1) < O (logn) < O (n) < O (n ^ 2) < O (n ^ C) < O (C ^ n)

Constant < logarithmic order < linear order < square order < polynomial order < exponential order

Constant order

Void aFunction () {

Int c = 10 + 20

Int d = c * c; printf (d)

}

Analysis: the amount of calculation is 2. 2 is a constant function, so it has little effect on the growth of constant function, so it is recorded as O (1).

Linear order

Void bFunction (int n) {

For (int I = 0 ~ (th) I < n ~ (th) I ~ +) {/ / n

Int c = 2 * I; / / 1

Int d = 3 * I; / / 2

}

}

Analysis: the amount of calculation of the function is equal to (n) (2), and the 2 constant is negligible, so it is recorded as O (n).

Square order

Void bFunction (int n) {

For (int I = 0 ~ (th) I < n ~ (th) I ~ +) {

For (int j = 0 * * j < I * * j +) {

}

}

}

Analysis: the amount of calculation of the whole function is (n) (n ^ 1), and the constant quantity is ignored, so it is written as O (n ^ 2).

Logarithmic order

Void bFunction (int n) {

For (int I = 3 * * I < n;) {

I * = 3;}

}

Analysis: suppose that the condition of the cycle s times is s = 3 ^ s < n; the logarithm is expressed as s = log3n, marked as O (log3n), and the constant can be ignored O (logn).

Multinomial order

Void bFunction (int n) {

For (int I = 0 ~ (th) I < n ~ (th) I ~ +) {

For (int j = 0 * * j < n * j +) {

For (int k = 0 * * k < n * k +) {

}

}

}

}

Analysis: the amount of calculation is n ^ 3, and the power is constant and recorded as O (n ^ C).

Exponential order

Void bFunction (int n) {

Int num = n

For (int I = 0 ~ (th) I < n ~ (th) I ~ +) {/ / O (n)

Num * = n

}

For (int j = 0 position j)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.