Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article also participated in the “Digitalstar Project” to win a creative gift package and creative incentive money

🛫 foreword: come at the beginning dig gold! Welcome to support! Learn from each other and grow from each other!

Specific about: time complexity and space complexity of the concept explained and rules, please old iron people move my last article! # Temporal complexity and spatial complexity of data structures

Analysis of classical examples of time complexity

The rules

Example 1: Loop

void Func1(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

Copy the code

Perform 2 x N+10 times

O(2 times N+10) ==>O(N)

Time complexity: O(N)

Example 2: Loop

void Func2(int N, int M)
{
	int count = 0;
	for (int k = 0; k < M; ++k)
	{
		++count;
	}
	for (int k = 0; k < N; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}
Copy the code

Execute M+N times in total. Since the size of M and N is unknown, the time complexity is O(M+N).

  • Case 1: M>>>N, then time complexity: O(M)
  • Case 2: N>>>M, then time complexity: O(N)
  • Case 3: M and N are about the same size, then the time complexity is O(M) or O(N).

Example 3: Loop

void Func3(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

Copy the code

100 times in total, constant times -> time complexity 0(1)

O(1) doesn’t mean the algorithm runs once, it runs a lot of times

Example 4: STRCHR

STRCHR Searches for characters in a string

Returns the position of the first occurrence of a character, NULL if not found

The simulation implements STRCHR

#include<stdio.h>
#include<assert.h>
char* my_strchr(const char* str, char c)
{
    assert(str);
    char* tmp = str;
    while (*tmp)
    {
        if (*tmp == c)
        {
            return tmp;
        }
        else{ tmp++; }}return NULL;
}
int main(a)
{
    char* str = "Mangoa";
    printf("%s\n", my_strchr(str, 'a'));
    return 0;
}
Copy the code

Back to business:

// Calculate STRCHR time complexity?
const char * strchr(const char * str, int character);
Copy the code

Best case: 1 find

Average: N over 2 times

Worst case: N searches

When an algorithm has different time complexities depending on the input, the time complexities make pessimistic predictions, worst-case scenarios.

So the time is order N.

Example 5: Bubble sort

Bubble sort idea: Compare adjacent elements

void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1; }}if (exchange == 0)
			break; }}Copy the code

So each bubble sort is going to have a number where it should be, and each bubble sort is going to have one element, N numbers, N minus one

First run: Compare N-1 numbers

Second run: Compare N-2 numbers

.

N-1st run: Compare 1 number

Arithmetic sequence: F(N) = N*(n-1)/2

So the time complexity is 0(N^2).

Example 6: Binary search (split search)

Binary search: reduce the search scope by 1/2 each time until it is found/not found

int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid;
		else
			return mid;
	}
	return - 1;
}
Copy the code

About binary search

Premise: Order

Find 1 number in 1000 -> Worst search times: 10

Find 1 number in 100W number -> Worst number of searches: 20

Finding a number in a billion -> Worst number of lookups: 30

2^10 = 1024
2^20Approximately equal to the100W is actually greater than100W
2^30Approximately equal to the10Hundred millionCopy the code

Q: What is the maximum number of times you can search for one person in an ordered population of 1.4 billion

31 times, 2 to the 31st is about 2 billionCopy the code

How recursive algorithms calculate time complexity:

Recursion times * Number of recursive calls per time

Example 7: Factorial recursion

// Calculate the time complexity of factorial recursive Fac?
long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1)*N;
}
Copy the code

Example number 8: Fibonacci sequence

// Calculate the time complexity of Fibonacci recursive Fib.
long long Fib(size_t N)
{
	if (N < 3)
		return 1;
	return Fib(N - 1) + Fib(N - 2);
}
Copy the code

Although F(n-1) and F(n-2) are both in the recursion of F(n), they are not called at the same time, they are called F(n-1) and then F(n-2).

So the number of recursive calls is: 1

Analysis of classical examples of spatial complexity

Example 1: Bubble sort

// Calculate the space complexity of BubbleSort.
void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1; }}if (exchange == 0)
			break; }}Copy the code

Extra constant Spaces: I and exchange and end

The exchange and I variables create space each time they enter the inner loop, and the space is destroyed when they exit the inner loop. And then you do this n times. ** is created again in the same place, essentially without being destroyed. ** only takes up that space, so it’s O(1) instead of O(N),

Example 2: Fibonacci series – Circular edition

// Calculate Fibonacci space complexity?
// Return the first n terms of the Fibonacci sequence
long long* Fibonacci(size_t n)
{
	if (n == 0)
		return NULL;
	long long * fibArray = (long long *)malloc((n + 1) * sizeof(long long));
	fibArray[0] = 0;
	fibArray[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
        // The last number is equal to the sum of the first two
		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
	}
	return fibArray;
}
Copy the code

N +1 extra space array, space complexity: 0(n)

The time is also 0(N), and the loop is executed N-1 times

Example 3: Find n factorial – recursively

== recursion: stack frame consumption depends on the depth of recursion ==

// Calculate the space complexity of factorial recursive Fac?
long long Fac(size_t N)
{
	if (N == 0)
		return 1;
	return Fac(N - 1)*N;
}
Copy the code

== Each recursive call opens function stack frame ==, opens a total of N stack frames, each stack frame uses constant space. So the space complexity is order N.

Space is reusable, but time is gone forever

Example 4: Fibonacci sequence – recursive version

// Calculate the space complexity of Fibonacci recursive Fib.
long long Fib(size_t N)
{
	if (N < 3)
		return 1;
	return Fib(N - 1) + Fib(N - 2);
}
Copy the code

At most N stack frames can be created, and no more than N stack frames can be created

So the space complexity is order N.

== recursion: stack frame consumption depends on the depth of recursion ==

Common complexity comparisons

Time complexity and space complexity examples are explained here, if you are helpful, welcome to support the blogger! We welcome your criticism and correction!