I love the summary of data structure and algorithm learning notes. I recorded them in accordance with the sequence of video learning. If there are any mistakes, please kindly comment.
I. What is an algorithm?
- An algorithm is a series of execution steps used to solve a particular problem
Fibonacci algorithm
- 1. What is Fibonacci?
/ / n bits of data value = n - 1 data value + n - 2 0,1,1,2,3,5,8,13...Copy the code
- 2. How many ways can I write it?
The first easy way
-(int)fib:(int) n {if (n<=1) {return n; @} / * * algorithm parse = = = = = = = = n - n bits of data values one data value + n - two data values * / return [self fib: n - 1] + [self fib: n - 2); }Copy the code
The second optimization scheme
-(int)sum2:(int) n {// if (n<=1) {return n; } /* @ algorithm parse ======= declare two variables first=0; Second =1; Represents the first bit of the data value I < n-1; I <n-1 sum = first + second; First = second; Second = sum; second = sum; Return second; * */ int first = 0; int second = 1; for (int i = 0; i < n-1; i++) { int sum = first+second; first = second; second = sum; } return second; }Copy the code
- 3. What’s the difference between the two methods?
- The first one works for small n, but once n gets a little bit bigger, this algorithm takes a lot of time because it’s called repeatedly
- The second method doesn’t discriminate between n sizes, even if N is large, this algorithm doesn’t take time
- The elapsed time of the two methods can be monitored by a specific tool, but HERE I’m out of luck
- Time complexity analysis of Fibo – Acci algorithm
Let’s look at the time complexity of the first method, which can be understood as, how many times to call the sum function, the time complexity is several. Let’s graph the call order
N = 1+2+4+8 = 2^0 +2 ^1 +2 ^2 +2 ^3 = 2^ 4-1 = 2^(n-1) -1 = 0.5 * 2^ n-1 time complexity: O(2^n)
The time complexity of the second method is O(n).
O(n) < O(2^n)
How to evaluate an algorithm?
- Accuracy, readability, robustness (ability to respond to unreasonable input)
- Time complexity: Estimating the number of times a program’s instructions are executed (execution time)
- Space complexity: The required storage space is estimated
Big O notation
- Complexity is usually described in the big O notation, which refers to the complexity of data size N
- Ignore constants, coefficients, low and logarithmic orders and generally omit the base
- 9 = O(1)
- 2n + 1 = O(n)
- n^2 + 2n + 1 = O(n^2)
- 4n^3 + n^2 + 2n + 1 = O(n^3)
- log2n = O(logn)
- 2nlog5n = O(nlogn)
- Common complexity
Time complexity comparison, the later shows that the higher the time complexity of O (1) < O (logn) < O (n) < O (nlogn) < O (n ^ 2) < O (n ^ 3) < O (2 ^ n) < O (n!) < O(n^n)
5. The optimization direction of the algorithm
- Use as little storage space as possible
- With as few execution steps as possible (execution time)
- Depending on the situation, you can think of space for time, time for space
6. Multiple data schemas
If you look at the algorithm below, the time complexity depends on both n and K
-(void)testn:(int)n k:(int)k { for (int i = 0; i<n; i++) { NSLog(@"n"); } for (int i = 0; i<k; i++) { NSLog(@"k"); }}Copy the code
Therefore, the time complexity of the above complex scale is O(n+ K). When it is complex scale, all factors should be taken into account.
This first record to The Times, if there are mistakes, feel free to comment.