Chapter I

1.1 calculation

Computers are just our tools ( means ), The object of our study is computing .

calculation = information processing

With some kind of tool , Follow certain rules , In a clear and mechanical form .

Machine model = computer = Information processing tools

So called algorithm , Under specific calculation model , A sequence of instructions designed to solve a specific problem

* input , Information to be processed ( problem )
* output , Processed information ( answer )
* Correctness , It can solve the specified problem
* certainty , Any algorithm can be described as a sequence of basic operations
* feasibility , Every basic operation can be realized , And completed in a constant time
* Poverty , For any input , Basic operation of economic development , You can get the output
Definition of good algorithm

* correct , Correct output for input
* robust , For illegal operation , Can resume normal execution of the program
* readable , Structured + Accurate naming + notes + ···
* efficiency , As fast as possible , As little storage as possible
program = data structure + algorithm

To improve or optimize an algorithm , We need to know the efficiency of this algorithm first .

algorithm analysis

* Correctness , Is the algorithm function consistent with the problem requirements
* cost , Running time + Required storage space
Generally, we take the worst case of the size of a metric for an algorithm .

For specific problems + Different algorithms , How can we judge its advantages and disadvantages ? Consider the following two models

* TM Model ( Turing machine ).
* RAM Model ( assembly ).
Our unit of measurement is CPU Execution times of , The algorithm needs to be reset when necessary .

large O mark

n Is the scale of the problem .

Constant coefficient can be ignored :
O(f(n))=O(c∗f(n))O(f(n))=O(c∗f(n))
Low order items can be ignored :O(na+nb)=O(na),a>b>0O(na+nb)=O(na),a>b>0

Other marks :

* Big Ω, Maximum lower bound .
* Big θ , compromise .
O Level of :

* constant ,O(1)
* logarithm ,O(logn), with 2 Base number
* polynomial ,O(n^c)
* Linear complexity ,O(n)
* Exponential complexity ,O(2^n)
Algorithm efficiency from O(2^n) reach O(n^c) It's a difficulty . under normal conditions , It's very difficult for us to find an efficient algorithm from exponential to polynomial . This is a watershed .

theorem :2-Subset is NP-complete. explain : As far as the current calculation model is concerned , There is no algorithm to answer this problem in polynomial time .

NP The problem is a power set problem , The efficiency is O(2^n).

algorithm analysis

Two main tasks = Correctness ( Invariance * Monotonicity ) + Complexity .

C++ Basic instructions of ISO high level languages , Are equivalent to RAM Basic instructions for ; In a gradual sense , They are roughly the same .

Main methods of complexity analysis :

* iteration : Summation of series

* arithmatic series : Same order as the square of the last term
* Power series : One order higher than power
* Geometric series : Same order as the last term
* Convergence series : constant O(1)( It makes sense in some cases , Like iterating to toss a coin , Until the front )
* Harmonic series :O(logn)
* Logarithmic series :O(nlogn)
* …( There is a book called 《 Concrete mathematics 》)
* recursion : Recursive trace + Recurrence equation
* guess + verification
Iteration and recursion

Iteration is artificial , Recursive square magic .

In terms of efficiency , The efficiency of iteration is higher than that of recursion . What we need to learn is a process from recursion to iteration .

To rule all is to rule few , So is the score .

For a question , Divide into a series of subproblems . By solving the subproblem, we can get the solution of this problem .

Reduce and govern and divide and govern .

dynamic programming

First example : Fibonacci series

Recursive version of fib And iterative fib There's a huge difference in efficiency ( Reason recalculated fib number ).
// Recursive version int fib(int n){ return (2>n)? n : fib(n-1) + fib(n-2); }
Obviously, this is a power set problem , The time complexity of this code is 2 Of n Power , Spatial complexity is O(n).

improvement 1: Memory version ( Tabulation )
// iteration int arr[] = new int[n+1]; arr[1] = 1; arr[2] = 1; for(int i=3;i<n;i++){
arr[i] = arr[i-1]+arr[i-2]; } return arr[n];
The above time complexity and space complexity are O(n).

improvement 2: dynamic programming ( Bottom up )
// iteration int f=0,g=1; while(0<n--){ g = g+f; f = g-f; } return g;
Time complexity is O(n), Spatial complexity is O(1).

Second example :LCS sequence

Recursive version ( Algorithm steps ):
For sequences A[0, n] and B[0, m] There are three situations

* if n= -1 or m= -1, Then take as empty sequence (“”)
* if A[n]= ‘X’ =B[n], Then take LCS( A[0,n), B[0,m) ) + ‘X’
* A[n] != B[n], Then in LCS( A[0,n], B[0,m)) And LCS( A[0,n), B[0,m]) Whichever is better public
static String LCS(char A[],int alo,int ahi,char B[],int blo,int bhi){ // The first situation if
(ahi==-1||bhi==-1){ return ""; } // The second situation if(A[ahi]==B[bhi]){ return
LCS(A,alo,ahi-1,B,blo,bhi-1)+A[ahi]; } // The third situation , Because of this situation, the problem is divided into 2 Subproblem . else{ String
AA = LCS(A,alo,ahi-1,B,blo,bhi); String BB = LCS(A,alo,ahi,B,blo,bhi-1); return
AA.length()>BB.length()? AA : BB; } }
Obviously a power set problem , So the time complexity is O(2^n), The space complexity is O(n).

Analysis by recursion , We come to a conclusion , Repeated element multiple calculation , So we can improve .

Iteration ( Tabulation ):

* The first row and column are initialized to 0
* If the letters corresponding to rows and columns are equal , be table[i][j] = table[i-1][j-1].
* table[i][j] take table[i-1][j] and table[i][j-1] The bigger public static void main
(String[] args) {// test data String A = "DATA"; String B = "NAA"; int n = A.length();
int m = B.length(); //start LCS // initialization int table[][] = new int[n+1][m+1]; for(int
i=0;i<n;i++){ table[i][0] = 0; } for(int j=0;j<m;j++){ table[0][j] = 0; } // iteration
for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){
// The second situation , Because the string is from 0 start , And the form is from 1 start , So for table And string difference 1 if(A.charAt(i-1)==B.charAt(j-1)){
table[i][j] = table[i-1][j-1]+1; } // The third situation else{ table[i][j] = table[i-1
][j]>table[i][j-1] ? table[i-1][j] :table[i][j-1]; } } } //end LCS // test result int
count =1; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(table[i][j]==count){
System.out.print(A.charAt(i-1)); count++; } } } System.out.println(); }
Obviously, both time complexity and space complexity are O(n*m).

Technology
©2019-2020 Toolsou All rights reserved,
Python Basic knowledge and notes Programmer Tanabata Valentine's Day confession code NOI2019 travels China's longest high speed rail officially opened ! The fastest way to finish the race 30.5 hour C Language programming to find a student's grade Software testing BUG describe ESP8266/ESP32 System : Optimize system startup time Unity Scene loading asynchronously ( Implementation of loading interface ) Baidu , Ali , Tencent's internal position level and salary structure , With job suggestions !PYTHON Summary of final review