Time complexity

Time complexity

1. Constant time operation

If an operation has nothing to do with the data volume of the sample , Every time is a fixed time to complete the operation , This operation is called a constant operation .

Example ：int a=arr[i]; a take i The number of positions is taken out , Is a fixed time , And arr It doesn't matter the amount of data , This is a constant operation .

conversely ,int b =list.get[i]; It's a linked list ,b Values need to be taken one by one from the beginning of the linked list ,i In the thousands , Just check how many people , It's about the amount of data , Not a constant operation .

Add, subtract, multiply and divide , Bit operations are all constant operations .

2. Time complexity

Time complexity is an algorithm flow , An indicator of the number of constant operations . Commonly used o Express , pronounce as big o.

say concretely , How many constant operations are performed in an algorithm flow ( use N Express ), Sum up the quantitative expression of constant operation (N The expression of ), Only the highest order terms are left , And not the coefficient of the highest order term , If the rest is f(N), So the time complexity is o(f(N)).

3. Evaluate the algorithm flow

Evaluate the flow of an algorithm , Let's look at the time complexity index first , Highest order items . If the same , Then analyze the actual running time under different data samples , That is to say “ Constant term time ”.( Just look at N The coefficient of the expression , If you N1 yes 10,N2 yes 100, however N2 Of 100 There are many bit operations in ,N1 Of 10 Middle is addition, subtraction, multiplication and division , Can't directly because 10<100 Just say N1 Better algorithm , Because the constant operation time of addition, subtraction, multiplication and division is different from that of bit operation , Not sure , We need to experiment with the actual situation .)

Encounter the same indicators , Directly by experiment , Run the code separately to judge .

Example ：

` public static void text1(){

​ int N =10000;

​ int a=0;

​ for(int i=0;i<N;i++){

​ a=12+100;

​ a=32*12;`

}

}

`public static void text2(){``

​ int N =10000;

​ int a=0;

​ for(int i=0;i<N;i++){

​ a=12|100;

​ a=746^12;

}

}

text1 and text2 The indicators of time complexity are the same N, Next, direct code tests to determine which is better , There is no need to go to the ratio coefficient .