What is a data structure
Data structure is the way that computers store and organize data, and there are one or more specific relationships between them
What is an algorithm
Algorithm: a well-defined calculation process that takes an input and produces an output
The algorithm is a series of calculation steps to convert the input data into the output results
Sorting is a common algorithm
Such as binary search
importance
OJ form of written examination for school recruitment
20-30 multiple-choice questions, 3-4 programming questions
In the school recruitment interview, the weight of data structure and algorithm is very high
Complexity
Algorithm efficiency
Time efficiency
Time complexity
concept
The execution times of basic operations in the algorithm is the time of the algorithm according to the complexity
The time complexity of the algorithm is a function
In practice, time cannot be really calculated (different machines / environments)
Eight cores, that is, eight CPUs and 64g memory
Dual core 4G
Asymptotic representation of large O
Time complexity calculation,large O Progressive representation of---estimate
2n^2+2n+10--->O(n^2)
n->∞Time,f(n)->n^2
The time complexity of the algorithm is a function,In the function expression,The most influential item
Big O notation large O Symbol
Take the highest order,And remove the coefficient
If it's a constant,then is O(1)
Fun(100) You can't think of it as O(1)
Look at the algorithm,Not a specific call
The value passed in by the function can be arbitrary
such as:
strchar("abcdef",'x');//In this call, the string length is 6. Is the complexity O(1)
O(M+N) M,N is a constant
Instead of O(1)
M N doesn't know who is big and who is small
O(1) indicates that it is constant times, and 10W and 100W are also O(1)
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<time.h>
int main()
{
int n = 100000000;
int begin = clock();
for (int i = 0; i < n; ++i)
{
}
int end = clock();
printf("%d\n", end - begin);
//clock displays the timestamp of the beginning of program execution, in milliseconds
//100 million times, only 39 Ms
return 0;
}
Ten thousand times or 100 million times are in the tens of milliseconds level
With the rapid development of hardware, CPU runs too fast
In time complexity calculation, it is usually assumed that the length of array / string is N
Find a data in an array with a length of N, the best time to find it, and the worst n times
Average N/2, but in this case, the default time complexity is the worst
O(N)
Bubble sort:
N-1+...+1=N(N-1)/2—>O(N^2)
void bubble_sort(int arr[], int sz)
{
int i = 0;
int j = 0;
//Number of trips
for ( i = 0; i < sz-1; i++)
{
//Each bubble sorting process
//10 elements 9 Comparison 8 pairs
//Logarithm to be compared - 1 per trip
for (j = 0; j < sz-1-i; j++)
{
if (arr[j+1] < arr[j])//Ascending order
//If it is a string sort, you cannot use the > < sign
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
practice
Interview question 17.04 Disappearing numbers
The array nums contains all integers from 0 to N, but one of them is missing. Please write code to find the missing integer. Do you have a way to finish it in O(n) time?
If the order of the first row is equal to the order of the second row, the order of the first row is equal to the order of the second row
Or qsort (quick sort) the bottom layer is O(N* logN), which does not meet O(N)
Train of thought 2:0~n calculate the sum of the arithmetic sequence - the addition of the values in the array
O(1) O(N)
Train of thought 2
int missingNumber(int* nums, int numsSize)
{
int n = numsSize+1;
int ret1 =0;
// All values between 0-n accumulate O(1)
for(int i = 0; i < n; i++)
{
ret1 += i;
}
int ret2 = 0;
// All values in the array are accumulated
for(int j = 0; j < numsSize ; j++)
{
ret2 += nums[j];
}
return ret1 - ret2;
}
//Time complexity O(N)
Train of thought 3
Train of thought 3: XOR
0~n Numbers and values in the array are XOR in turn,The result is the missing number
Two identical numbers XOR==0
9 6 4 2 3 5 7 0 1
0 1 2 3 4 5 6 7 8 9
There are only 8 left in XOR
No sorting is required
[3 0 1]
0 1 2 3
3---0011
0---0000
3^0->0011 3
3^0^1-->0011^0001-->0010-->2
0010^0000-->0010
0010^0001-->0011
0011^0010-->0001
0001^0011-->0010--->2
3^0^1^0^1^2^3--->2
1^3^1--->3
There is no need to consider the order of XOR. As long as the final two XORs of the same number are eliminated
int missingNumber(int* nums, int numsSize)
{
int x = 0;
for(int i = 0; i < numsSize + 1; ++i)
{
x ^= i;
}
for(int j = 0; j < numsSize; ++j)
{
x ^= nums[j];
}
return x;
}
//This makes it clearer
int missingNumber(int* nums, int numsSize)
{
int x = 0;
for(int i = 0; i < numsSize + 1; ++i)
{
x ^= i;
if(i < numsSize)
{
x ^= nums[i];
}
}
return x;
}
//Form of a cycle
136. Figures that appear only once
Instead of using extra space, it represents a constant space
Linear time complexity, i.e. O(N)
int singleNumber(int* nums, int numsSize)
{
int x = 0;
for(int i = 0; i<numsSize; i++)
{
x ^= nums[i];
}
return x;
}
Sword finger Offer 56 - I. the number of occurrences of numbers in the array
In an integer array nums, except for two numbers, other numbers appear twice. Please write a program to find these two numbers that only appear once. The time complexity is O(n) and the space complexity is O(1).
ret = 0, XOR all numbers in the array with ret
This eliminates the number of occurrences twice
ret=x^y
2.
ret must not be 0. Find any bit in ret that is 1, indicating that one of the corresponding bits of X and Y is 1 and one is 0
Divide the number in the original array into 1 group if the nth bit is 1 and 0 group if the nth bit is 0
1 3 1 2 5 2
For example, the first digit is 1 and divided into a group, and the first digit is 0 and divided into a group
3 2 2 1 1 5
And then separate them from XOR
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
//returnSize means that the two numbers found are returned in the form of an array
int* singleNumbers(int* nums, int numsSize, int* returnSize)
{
int ret = 0;
for(int i = 0; i < numsSize; i++)
{
ret ^= nums[i];
}
//Find a bit with 1 in ret
int j = 0;
for(; j < 32; ++j)
{
if(ret & (1<<j)) // if(ret>>j & 1)y
{
break;
}
// The j-th bit of ret is 1, indicating that the j-th bits of X and y are 1 and 0
}
// The original array is divided into two groups, a group with bit j as 1 and a group with bit j as 0
//X and y will enter group a and group b respectively. Other numbers that appear twice will either enter group a or group b
//The data of group a and group b will be changed into other numbers, which will appear twice, and only one number will appear once, and then XOR respectively
int x = 0;
int y = 0;
for(int k = 0; k < numsSize; ++k)
{
if(nums[k] & (1<<j)) //Group a
{
x ^= nums[k];
}
else //Group b
{
y ^= nums[k];
}
}
int* arr = (int*)malloc(sizeof(int)*2);
arr[0] = x;
arr[1] = y;
*returnSize = 2;//Output type parameter, let the outside get the array length
return arr;
}
Note: the more strict compiler does not allow the 1 of int to shift 31 bits to the left, because it will run to the symbol bit
You can consider moving to the right
Or cast to another type, long long or unsigned int
Sword finger Offer II 004 A number that appears only once
Give you an integer array nums. Except that an element appears only once, every other element appears * * three times** Please find and return the element that appears only once.
int singleNumber(int* nums, int numsSize)
{
unsigned int arr[32] = {0};
//int is the highest signed bit, and the valid data is only 31 bits
//After changing to unsigned, all bits are data bits
int count = 0;
int k = 31;
for(int i = 0;i < 32;i++)
{
for(int j = 0;j < numsSize;j++)
{
count += ((nums[j]>>i) & 1);
}
arr[k] = count;
count = 0;
k--;
}
for(int i = 0;i < 32;i++)
{
arr[i] %= 3;
}
int ret = 0;
for(int i = 0;i < 32;i++)
{
ret |=(arr[31-i]<<i); //Compilation failed on Leetcode here
}
return ret;
}
Idea:
Since the number of other numbers is odd this time, all XOR together cannot eliminate the remaining numbers. So we have to change the way.
Add up each binary bit of all the numbers in the array into an array, and then%3, the final number is the number that appears only once.
Since other numbers appear three times, their binary bit must be a multiple of 3.% 3 is equivalent to subtracting all the repeated bits, and the remaining binary bits are the binary bits of numbers that appear only once.
Steps:
First, use bitwise and to take out each binary bit and add it into the array
Then all the numbers in the array are% 3
Operate the numbers in the array on ret by bitwise OR
//int is the highest signed bit, and the valid data is only 31 bits //After changing to unsigned, all bits are data bits
//Write together succinctly
int singleNumber(int *nums, int numsSize) {
int ans = 0;
for (int i = 0; i < 32; ++i) {
int total = 0;
for (int j = 0; j < numsSize; ++j) {
total += ((nums[j] >> i) & 1);
}
if (total % 3) {
ans |= (1u << i);
}
}
return ans;
}
Binary search
Best: O(1)
Binary search is also called half search
In terms of time complexity, it is used to be abbreviated as logN
Some data will be written as lgN. Strictly speaking, this is wrong. It is confused with mathematics
Binary search requires data to be sorted first
You can use qsort to sort quickly
Sort first – > binary search
qsort time complexity N* logN
Binary search logN
After sorting, the binary search is fast and convenient for multiple searches
The red black tree / hash table is the real algorithm for searching
recursive algorithm
Time complexity of recursive algorithm = number of recursions * number of times in each recursive function
Fac(N)–>Fac(N-1)–>...Fac(1)
That is, N*1(1 represents constant times)
Time complexity O(N)
If another for loop is set, it is O(N^2)
Fibonacci sequence
Note that the Fib completed in advance needs to be subtracted, which can be ignored
You can estimate the CPU operating efficiency, which is generally 100 million
2 ^ 30 is about 1 billion
#include<time.h>
long long Fibonacci(size_t N)
{
return N < 2 ? N : Fibonacci(N - 1) + Fibonacci(N - 2);
}
int main()
{
int begin = clock();
Fibonacci(40);
int end = clock();
printf("%d\n", end - begin);
}
/*
40 Calculate 3339ms,45 calculate 36351ms
The time complexity of this algorithm is too high, which is meaningless in practice
O(2^N)
Consider changing to cycle -- > O (n)
*/
#include<stdio.h>
//Complexity O(N)
int fib(int n)
{
int a = 1;
int b = 1;
int c = 1;//n = 1/2 return directly to 1 without going through the cycle
while (n > 2)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = fib(n);
printf("%d\n", ret);
return 0;
}
Spatial complexity
With the development of technology, the requirements for space are relatively low, and we don't pay much attention to the complexity of space
Space complexity is not to calculate how many bytes the program occupies
It's the number of variables
Bubble sorting
Bubble sort space complexity O(1) - constant space
The input number is not considered, but the extra space in the operation of the algorithm is considered
Time is cumulative, space is not cumulative, and space can be reused
The space was used for the first time. After the destruction, the space was used for the next time
Fibonacci
Open n+1 space is O(N)
The complexity is not considered for a call, but for the algorithm
recursion
Each call creates a function stack frame
There is a constant space in each stack frame
