What is a data structure

== Is to implement some projects , Need to store data in memory ==

The time and space complexity of the algorithm

1. Algorithm efficiency

2. Time complexity

3. Spatial complexity

4. Common time complexity and complexity oj practice

1. Algorithm efficiency

How to measure the quality of an algorithm

For example, the Fibonacci sequence below

long long Fib(int N){    if(N < 3)    	return 1;    return Fib(N-1) + Fib(N-2);}

== Algorithm complexity ==

After the algorithm is written into an executable program , Runtime takes time, resources and space ( Memory ) resources .== So measure the quality of an algorithm ==, Usually from == Time == and == Space == Measured in two dimensions ,== That is, time complexity and space complexity .==
== Time complexity mainly measures the running speed of an algorithm , The spatial complexity mainly measures the additional space required for the operation of an algorithm .== In the early days of computer development , The storage capacity of the computer is very small . So I care about space complexity . But after the rapid development of the computer industry , The storage capacity of the computer has reached a high level . So now we don't need to pay special attention to the spatial complexity of an algorithm .

Time complexity

The concept of time complexity

Definition of time complexity ： In computer science ,== The time complexity of the algorithm is a function ==, It quantitatively describes the running time of the algorithm . The time that an algorithm takes to execute , In theory , It can't be worked out , Only you put your program on the machine and run , To know . But do we need to test every algorithm on the computer ？ It can be tested on the computer , But it's a lot of trouble , That's why we have the time complexity analysis . The time taken by an algorithm is proportional to the number of statements executed ,== The number of times the basic operations in the algorithm are executed , Time complexity of the algorithm .==

Be careful ：

1.== The function here is a function expression with unknowns in Mathematics ,==

2.== And we're not talking about seconds , It means several times ==

Because the machines are different （ yes , we have 2 nucleus , There is one core ）, The specific running time is different , So there is no way to measure time complexity with time

//  Please calculate Func1 in ++count How many times did the statement execute in total ？void Func1(int N){    int count = 0;    for (int i = 0; i < N ; ++ i)    {    	for (int j = 0; j < N ; ++ j)        {       	 	++count;        }    }        for (int k = 0; k < 2 * N ; ++ k)        {      		++count;        }        int M = 10;        while (M--)        {            ++count;        }    printf("%d\n", count);}

In practice, when we calculate the time complexity , We don't really have to calculate the exact number of execution , And only needs. == Approximate number of executions , So here we use big O The progressive representation of .==

Big O The progressive representation of

== Big O Symbol （Big O notation）： Is a mathematical symbol used to describe the progressive behavior of a function .==

Derivation is great O Order method ：

1. With constant 1 Replace all the addition constants in runtime

2. In the modified run times function , Only the highest order terms .

3. If the highest order term exists and is not 1, The constant multiplied by this item is removed . The result is big O rank

In addition, some algorithms have the best time complexity , Average and worst case

== The worst ：== Maximum number of runs of any input size （ upper bound ）

== On average ：== Expected number of runs of any input size

== The best situation ：== Minimum number of runs of any input size ( next )

In practice, the general concern is the worst-case operation of the algorithm , Therefore, the time complexity of searching data in the array is O(N)

example

example 1

//  Calculation Func2 Time complexity of ？void Func2(int N){	int count = 0;	for (int k = 0; k < 2 * N; ++k)	{		++count;	}	int M = 10;	while (M--)	{		++count;	}	printf("%d\n", count);}

example 2

//  Calculation Func3 Time complexity of ？void Func3(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);}

example 3

//  Calculation Func4 Time complexity of ？void Func4(int N){	int count = 0;	for (int k = 0; k < 100; ++k)	{		++count;	}	printf("%d\n", count);}

example 4

//  Calculation strchr Time complexity of ？const char* strchr(const char* str, int character);

example 5

#include<stdio.h>//  Calculation BubbleSort Time complexity of ？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;	}}

example 6

== To calculate the time complexity, you can't just look at a few layers of loops , But to see his thoughts ==

//  Calculation BinarySearch Time complexity of ？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;}

example 7

#include<stdio.h>//  Compute factorial recursion Fac Time complexity of ？long long Fac(size_t N){	if (0 == N)		return 1;	return Fac(N - 1) * N;}

example 8

== We should know that the time of time complexity is not reused ==

#include<stdio.h>//  Compute Fibonacci recursion Fib Time complexity of ？long long Fib(size_t N){  if (N < 3)      return 1;  return Fib(N - 1) + Fib(N - 2);}

Spatial complexity

Spatial complexity is also a mathematical expression , Is an algorithm in the process of running == A measure of how much extra storage space is temporarily occupied .== Space complexity is not how much the program takes up bytes Space , Because it doesn't make much sense either ,== So spatial complexity is the number of variables ==. Spatial complexity calculation rules are basically similar to practical complexity ,== Also use large O Progressive representation ==

== Be careful ==：

Stack space required for function runtime ( Store parameters 、 local variable 、 Some register information, etc ) It has been determined during compilation , Therefore, the spatial complexity is mainly determined by the additional space explicitly requested by the function at run time .

example

example 1

#include<stdio.h>//  Calculation BubbleSort Spatial complexity of ？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;	}}

example 2

#include<stdio.h>//  Calculation Fibonacci Spatial complexity of ？//  Returns the first of the Fibonacci sequence n term 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)	{		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];	}	return fibArray;}

example 3

== The consumption of stack frames depends on the depth of recursion ==

#include<stdio.h>//  Compute factorial recursion Fac Spatial complexity of ？long long Fac(size_t N){	if (N == 0)		return 1;	return Fac(N - 1) * N;}

== The stack is not very big ==

example 4

== Space can be reused , Not cumulative . Time is not reused , Cumulative . This sentence is time complexity , The essence of spatial complexity ==

#include<stdio.h>//  Compute Fibonacci recursion Fib Spatial complexity of ？long long Fib(size_t N){  if (N < 3)      return 1;  return Fib(N - 1) + Fib(N - 2);}

Common complexity comparison

Complexity OJ practice

1. Missing numbers

** Train of thought ：** Many people think that this problem is to sort and then go through it from small to large ==qsort Quick line up –》 Time complexity O(N*log2N), Obviously not meeting the conditions ==

** Train of thought two ：** This idea is combined with array subscripts ,== Arrays are good and basically odd ,==（0+1+2+…+n）-（nums[0]+nums[1]+nums[2]+…+nums[n-1]）

** Train of thought three ：** And it's very similar to the idea above , Create a （n+1） Array

** Train of thought four ：** Google interview questions tested similar Create a variable x=0, Give Way x And [0,n] All XOR again , And again , The XOR in the array is repeated ,== Then I'll XOR the last number again ==, final x That's what we're missing == We know that if two numbers are the same, the XOR is gone ==

2. Rotated array

== Did you find out? Haha, idea one is always the practice of college students , Always violent , Simple and crude method ==

** Train of thought ：** Violent solution rotation k Time The time complexity is O(N*K) Spatial complexity O(1)

** Train of thought two ：** Open up extra space ,== Trade space for time , This is also a better way == Time complexity O(N) Spatial complexity O(N), But it doesn't meet the requirements of the topic , There is more space than

** Train of thought three ：** It's awesome , stay 《 Basic training of programmers 》 There seems to be this problem on it == Three step flip ==, Flip the front , Flip back , Then flip the whole == Daniel came up with an efficient method ==

Time complexity O(N) Spatial complexity O(1)