Data structures and algorithms – time and space complexity analysis

How to judge a data structure or algorithm

How do you judge a data structure or algorithm? It’s just a matter of running fast and using up memory. So execution efficiency and memory consumption are indicators of algorithms, right? So how do we evaluate execution efficiency and memory consumption?

Here are a few code examples. Which group has the shortest running time?

def printInfo() :
	print("hello world")

def printInfo_2(n) :
    for i in range(n):
    	print("hello world")

def printInfo_3(n) :
    for i in range(n):
        for j in range(n):
            print("hello world")
Copy the code

It’s almost safe to say that our printInfo() method is the shortest and most efficient. Is running time a proxy for running efficiency? There are some problems here.

1. Run results depend on the run environment

   The difference in the running environment and the hardware has a big impact on the results. We run the same code, and if an Intel Core I9 processor is running on an Intel Core I3 processor, it goes without saying that the i9 is running faster than the i3. Not only the processor, but also memory, mechanical and solid-state drives, networks, traffic, and so on.

2. Run results depend on problem size

   In the example above, if we call printInfo_2() and printInfo_3() with 1, it will take the same time to execute as if we had called printInfo() directly. Because the data size is the same, it’s all 1. The size of the problem also affects the structure of the operation.

So, we need a way to roughly calculate the efficiency of an algorithm without running specific data, or even without running code, and that’s what we need to talk about time and space complexity.

Time complexity

What is time complexity?

What is time complexity? Before we define it, let’s think about some examples of estimating time in our lives.

It can be found that when we estimate time in life, we always take a number and a unit, and this number represents a approximate number. For time complexity, we can also refer to a similar method to predict the operation efficiency of the method.

Time complexity is a measure of the running time of an algorithm and only represents the trend of code execution time as data size increases. It is also called progressive time complexity and is denoted by O.

O(1), O(n^2).

Common time complexity

N indicates the size of the problem, in order of complexity

• Constant(Constant level) Time: O(1)

• Dsmt4 (Logarithmic) Time: O(log(n)).

• Linear Time: O(n)

• Linearithmic(Linear logarithmic) Time: O(nlogn)

• Quadratic Time: O(n^2)

• Cubic(Cubic) Time: O(n^3)

• O(b^n), b > 1

• Factorial Time: O(n!)

How do YOU calculate time complexity

def cal() :
	n = 100
	m = 1000
	return sum = n + m
Copy the code

If I call CAL (), is that O(3)?

Answer: Usually we ignore coefficients and constant terms, so if CAL () is called, the time complexity is O(1).

def loop() :
    for i in range(10) :print("hello world")
Copy the code

Answer: The time complexity is still O(1). Why? Even if it’s a loop, the data size is fixed, it’s only going to loop ten times, so the time is O(10 times 1), and since 10 is a coefficient and 1 is a unit, ignoring the coefficient, the time is still O(1).

def loop(n) :
    for i in range(0, n, 2) :print("hello world")
Copy the code

Answer: The time complexity is O(n), each time the value of I is increased by 2, so there is a total of F (n)=n/2 times, the time complexity is O(f(n)), ignoring the coefficient, the time complexity is O(n).

def cal_2(n) :
    for i in range(n):
        print("hello world")
        for j in range(n):
            print("hello world")
Copy the code

Answer: O(n^2), f(n) = n * (1 + n)= n^2 + n times, so time is O(f(n)), we usually pick the highest term, so time is O(n^2).

# O(logn): log time complexity
i = 1
while(i <= n){
    print(i)
    i *= 2
}
Copy the code

Answer: time is O(logn), f(n) = log2 n, ignoring the base, time is O(logn).

def loop(n) :
    for i in range(n):
        print("hello world")
    	for j in range(3 * n):
             print("hello world")
        for i in range(2 * n):
            print("hello world")
Copy the code

F (n) = n * (3n + 2n) = 3n^2 + 2n^2 = 5n^2

def loop(n) :
     for i in range(n):
        print("hello world")
    	for j in range(3 * n):
             print("hello world")
        for m in range(10) :print("hello world")
        for x in range(n*n):
            print("hello world")    
Copy the code

F (n) = N * (3n + 10 + n^2) = N ^3 + 3n^2 + 10n, the time complexity is O(n^3 + 3n^2 + 10n), ignore the coefficient, so the time complexity is O(n^3).

def fib(n) {if n< = 2:
        return n
    return fib(n - 1) + fib(n - 2);
Copy the code

Answer: O(2^n), the mathematical formula F (n) = F (n-1) + f(n-2), need to use mathematical induction.

def permutations(ls, start, end) :
    if(start >= end):
        print(ls)
    else:
        for i in range(start, end + 1):
            ls[start], ls[i] = ls[i], ls[start]
            permutations(ls, start + 1, end)
            ls[start], ls[i] = ls[i], ls[start]
Copy the code

Answer: O (n!

def cal(int m, int n) :
    sum_1 = 0
    for i in range(m):
        sum_1 += i
    sum_2 = 0
    for j in range(n):
        sum_2 += i
    return sum_1 + sum_2
Copy the code

Answer: O(m + n)

Time complexity analysis method

• We tend to ignore coefficients, constant terms, bases.
• By focusing only on the piece of code that executes the most times, you’re essentially taking the most times.
• If the size of the problem is n, the half operation is nlognThe series,mA layer nested loop isn^k.
• The rule of addition: the total time complexity is equal to the time complexity of the code with the largest magnitude, and the sibling loop is additive.
• The rule of multiplication: the complexity of nested code is equal to the product of the complexity of both inside and outside the nested code.

Pay attention to

When analyzing the time complexity, we also need to analyze the best and worst time complexity of this algorithm.

• Best time complexity: In the best case, the time complexity of the algorithm to run
• Worst time complexity: In the worst case, the time complexity for the algorithm to run

For example, the sorting algorithm, such as bubble sort, is O(1) in the best case, which is perfectly ordered, which is the ideal case. The worst time complexity is O(n^2), which is the worst case where [5,4,3,2,1] needs to be sorted into [1,2,3,4,5] in full reverse order. In particular, the worst time complexity is also an important indicator of the quality of the reference algorithm.

Spatial complexity

Spatial complexity is a measure of how much storage an algorithm temporarily occupies while running. Also progressively common O(1),O(n),O(n^2)

!!!!! Important idea: space for time (dimension), improve operation efficiency. Consider map-Reduce, a distributed computing architecture that distributes a complex problem to different machines to improve computing efficiency.