1. The significance of time complexity

For example, for the realization of the same function a, B two pieces of code, where

• A the execution takes 100ms and occupies 10MB memory
• B it takes 100 seconds and occupies 100MB memory

It’s clear that code A is better than code B. As you can see, code is measured by two metrics: elapsed time and memory footprint

This method of calculating the execution time and memory footprint of the code by executing it is called post-hoc statistics.

This statistical method is completely correct, but it has major limitations, such as:

1. I run it on machines with different configurations (such as I3, I9, R9, etc.). Due to the difference of CPU, the results must be biased, and the execution time of code B may even be better than that of code A;

2. For the same code, different input parameters (such as data size and order degree) may cause deviation in the execution result.

So we need a way to roughly estimate the efficiency of code execution without requiring specific test data to execute the test code.

Based on this requirement, let’s look at a piece of code:

public int calculate(int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum = sum + i;
    }
    return sum;
}
Copy the code

Let’s assume that each line of code has the same execution time, unit_time. Based on this assumption, calculate the total execution time of this code. Ok?

Line 2 requires a unit_time,

Lines 3 and 4 need to be executed n times, 2nunit_time,,

The total execution time of all this code is (2n + 1) unit_time, which is proportional to the number of times each line of code executes.

It can be expressed as follows: the code execution time T(n) is proportional to the execution times f(n) of each line of code, where T(n) is the execution time, f(n) is the sum of the code execution times, and N represents the data size.

2. Operation times

As for the number of code operations, we use the pool problem we did in primary school to make a metaphor:

Case 1: a water pipe can fill a pool of water in 2 days. How many days does it take to fill 10 pools?

2 x 10 = 20 days.

If you need to fill n pools, it takes 2 times n = 2n days.

The relative time is calculated using a function T(n) = 2n

Case 2: Fill 1 pool on the first day, 2 on the second day, 4 on the third day… On what day can I fill 32 pools (not concerts)?

Let’s use simple code to explain:

// Count the first day as 1
// The total amount of water discharged is n, n is 32
int count = 1;
while(count <= n) {
    count = count * 2;
}
Copy the code

The value of the variable count starts at 1 and is multiplied by 2 for each loop, using the logarithm of high school. The value of count for each loop is:

2º 2¹ 2² 2³ … 2ⁱ = n

We need to count the number of times the loop block is executed, using 2ⁱ = n, I =logn, which is T(n) =logn.

Let’s test it out in the case

By day 6, you can fill 32 pools of water

Case 3: There are water plant A and B, water plant A can fill A pool of water every day, water plant B can fill A pool of water every two days, ask water plant B to fill A pool of water how many days?

Well, 2 days, it doesn’t matter what A is, T(n) = 2

Case 4: Fill 1 pool on the first day, 2 on the second day, 3 on the third day, 1 more pool on the day before, by the 10th day, how many pools have been filled?

A: 1 + 2 + 3 + 4 +… + 10 = 55

So how to calculate the n day, this time used the high school learned the summation formula: 1+2+3+… + n = n (n + 1) / 2 = 1/2 level (n squared + n),

T (n) = 1/2 level (n + n squared)

The above examples correspond to several implementations:

Case 1: T(n) = 2n, the number of executions increases linearly;

Case 2: T(n) = logn, the number of executions increases logarithmically;

Case 3: T(n) = 2, the number of executions is a constant increase;

Case 4: T(n) = ½(n²+n), the number of executions increases;

3. Progressive time complexity

After obtaining the execution times T(n) of the basic operation, the calculation of the execution time is still not clear. As shown in cases 1 and 4, T(n) = 2n, T(n) = ½(n²+n), the value of n will affect the final result. For example, when T(n) = 233n, T(n) = 4n², n<50, The first value is bigger, the second value is bigger when n is greater than 60, and the final value of T(n) depends on the value of n.

When the value of n is large and close to infinity, constants, low-order values and coefficients in the publicity will not affect the growth trend of the final result and can be ignored. This method is called progressive time complexity, or time complexity for short, and is represented by big O. It describes the tendency of code to grow with data size, not the actual execution time.

When analyzing the time complexity of an algorithm, we only focus on the code with the most times of execution, where the time complexity of constant is O(1). Let’s analyze the time complexity of the above 4 cases:

Case 1:2n, after ignoring the coefficient, T(n) = O(n);

Case 2: logn, don’t ignore, T(n) = O(logn);

In case 3:2, the time complexity of constant is O(1), T(n) = O(1);

Case 4: ½(n²+n), i.e. ½n²+½ N, ignoring the lower order remaining ½n², ignoring the coefficient, T(n) = O(n²);

Let’s look at the trend of time complexity in the chart:Linear growth trendLogarithmic trendConstant growth trendSquare growth trend

4. Add: Space complexity

Time complexity describes the growth trend between algorithm execution time and data size, and space complexity describes the growth trend between algorithm storage space usage and data size.

For example, reverse an array:

public int[] reverse(int[] a) {
    int index = 0;
    int[] b = new int[a.length];
    for (int i = a.length; i > 0; i--) {
        b[index++] = a[i];
    }
    return b;
}
Copy the code

In this code, we declare a variable index, which occupies one unit of storage space. After that, we apply for an int array B with size N, which uses n space, and no new space is occupied. To sum up: the space occupied by index is constant and can be ignored.

5. To summarize

Code is measured by two metrics: elapsed time and memory footprint, as discussed in this article.

Time complexity and spatial complexity are used to analyze the direct growth trend of algorithm execution efficiency and data size, which can be roughly summarized as: The higher the algorithm order, the lower the execution efficiency.

Today’s content is also the basic content that needs to be paid more attention to in the process of brushing questions. There will also be some data structure or algorithm analysis in the future. With multiple brushing questions, I believe I will become more and more proficient.