One , Relevant

Time complexity ： Time taken to execute the current algorithm , Remember to do that T(n) = O(f(n))

Spatial complexity ： A measure of the amount of storage space temporarily occupied by an algorithm during operation , Remember to do S(n)=O(f(n))

summary ： Time complexity refers to the number of statement executions , Space complexity refers to the storage space occupied by the algorithm

Two , Time complexity

1. computing method

* Constant used 1 Replace all addition constants in runtime

* In the modified run times function , Keep only the highest order items

* Coefficient of removing the highest order term

2. Common complexity

Low to high complexity examples

O(1)： Constant order

public void Constant(int n){ int i = n+1;// Only one calculation is required , Time complexity and n Irrelevant

System.out.println(i); }

O(logn)： Logarithmic order

public static void logarithm(int n){ for (int i = 1;i < n;i = 2*i){

System.out.println(i); } }

In the above method , Set execution times to x, The last execution is with a remainder of m, Then there are ：x^2 + m = n, Constant terms are not considered in the calculation of time complexity , So about T(n) Yes ：x^2

= n, that x=log2n, That is to say, at this time T(n)=log2n

O(n)： Linear order

public static void linear(int n){// Linear order for (int i = 0;i<n;i++){// The number of program execution times and n Relationship

System.out.println(i); } }

O(n^2)： Square order

public static void square(int n){// Print from 1*1 reach n*n Multiplication table for (int i = 1;i<n+1;i++){

for (int m = 1;m<n+1;m++){ System.out.print(i+"*"+m+"="+i*m+" "); }

System.out.println(); } }

The square upgrade has k Order of second order

O(2^n)： Exponential order （m It's a constant ）

public static long index(int n){ if (n <= 1){ return 1; }else { return

index(n-1)+index(n-2); } }

As can be seen from the program ,T(0)=T(1)=1, meanwhile T(n) = T(n - 1) + T(n - 2) + 1, There 1 It's one of the addition operations . Obviously

T(n) = T(n - 1) + T(n - 2) It's a Fibonacci series , It can be proved by inductive proof , When n >= 1 Time T(n) < (5/3)^n, At the same time

n > 4 Time T(n) >= (3/2)^n. So the time complexity of this method can be expressed as O((5/3)^n), After simplification O(2^n).

3. Worst time complexity and average time complexity

The worst-case time complexity is called the worst-case time complexity . Generally not specified , The time complexity discussed is the worst case time complexity .

Average time complexity refers to the case that all possible input instances occur with equal probability , Expected running time of algorithm . Let the probability of each situation be pi, The average time complexity is sum(pi*f(n))

Three , Spatial complexity

1. Relevant

In general, space complexity is not considered , Spatial complexity does not mean the space occupied by all data , But the size of the secondary space used , For example, the operation of two matrices , An intermediate matrix is set in the middle to save some data , These spaces are called space complexity . The calculation of space complexity is very troublesome , The general simple algorithm space complexity is O(1).

2. Common space complexity

O(1)

public static void constant(int n){// Constant order int i = n+1; System.out.println(i); }

whether n Why value? , The temporary space required for execution does not follow a variable n The size of , That is to say, the space complexity of this algorithm is a constant , Can be expressed as O(1)

O(n)

public static void linear(int n){// Linear order int[] m = new int[n]; }

Simple to understand , In this method , Space needed and n It's linear

Four , summary

For a given algorithm , We have to do it.

Two analyses . The first is to prove the correctness of the algorithm mathematically , This step mainly uses the method of formal proof and related reasoning mode , Such as loop invariant , Mathematical induction, etc . On the basis of proving that the algorithm is correct , The second part is to analyze the time complexity of the algorithm . The time complexity of the algorithm reflects the magnitude of the increase of program execution time with the increase of input scale , To a great extent, it can well reflect the advantages and disadvantages of the algorithm . therefore , As a programmer , It is necessary to master the basic algorithm time complexity analysis method .

Technology

Daily Recommendation

views 26

views 2

©2019-2020 Toolsou All rights reserved,

Python Garbage collection and memory leak hive Summary of processing methods for a large number of small files The difference between memory overflow and memory leak , Causes and Solutions Create data mysql Library process You don't know ——HarmonyOS stay Vue Use in Web WorkerSparkSQL Achieve partition overlay write msf Generate Trojan horse attack android mobile phone Linux Page replacement algorithm C Language implementation Django Personal blog building tutorial --- Time classified archiving