- 2020-06-03 05:11
*views 3*- algorithm

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

- Java378 articles
- Python197 articles
- Linux110 articles
- MySQL83 articles
- Vue78 articles
- SpringBoot68 articles
- Spring61 articles
- javascript56 articles
- more...

Daily Recommendation

views 2

©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