Some new ideas about time complexity

1. Time complexity

1. Generally, the time complexity only considers the worst case
2. The time complexity of recursion is related to the depth of recursion . Such as calculating factorial ：

 
//  Compute factorial recursion Fac Time complexity of ？
long long Fac(size_t N)
{
    
	if (0 == N)
		return 1;
 
	return Fac(N - 1) * N;
}

Recursion N Time , Each time a new function stack frame is opened , For example Fn, need Fn-1, Continue down to f1, Open up the following stack frame, and the upper stack frame is still in use , Because of the above Fn, Wait for the following return , So the complexity is N. So the complexity of space is N
3. The time complexity of Fibonacci sequence is :O(n).
Recall the bottom oblique triangle . Shared by painting trees N layer . Sum the number of calculations and N relevant

4. The best case for bubble sorting is O(N), The first round of bubbling Set the tag variable , If exchage Never changed , The statement is in order , There is no need to walk repeatedly , The code implementation is as follows ：

//  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;
 }
}

The number of force buckles disappearing ：

https://leetcode.cn/problems/missing-number-lcci/
Array nums Contains from 0 To n All integers of , But one of them is missing . Please write code to find the missing integer . You have a way O(n) Is it finished in time ？
Ideas ： It's actually a math problem

1. Calculation 0~n And ：( The first + tail )*n/2.
2. Traverse and subtract all the numbers in the array , The residual value is missing .

The number of occurrences of numbers in an array

https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
Ideas ：

1. The result of all digital XORs , In fact, it is the result of the XOR of two different numbers , But where two numbers are different , The binary form of their XOR result must have a bit 1, XOR is easy to do , loop ^, So let's find this first 1 Where? ： Move right i position , Look and see 1 The result is 1.
2. According to what is said above 1 The position of is divided into two groups of numbers , Of these two sets of numbers , Each contains a single occurrence number , The remaining figures appear twice .

for (int i = 1; i < 32; i++)
	{
    
		//  Shift right and 1 Is a bit value 
		if ((ans >> i) & 1 == 1)
		{
    
			pos = i;
			break;
		}
	}```

3. Cycle through each number , If this bit matches, it will be shifted to 1&1==1, be

if ((* (nums + i) >> pos & 1)== 1)
		{
    
			s1^=*(nums+i);
		}

4. As long as there is a single occurrence of the number , use ret Another XOR will get . Because a number is XOR twice a number , Get yourself .