算法初接触1

算法第一弹
之前对算法接触的很少，没有一个明确的规划，也不太理解该学些什么，第一周就先简单总结一下吧。
算法中有算法复杂度，而算法复杂度又分为时间复杂度和空间复杂度：
①时间复杂度是指执行算法所需要的计算工作量。
②而空间复杂度是指执行这个算法所需要的内存空间。
时间复杂度一般与算法中执行次数成正比，一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。随着问题规模n的不断增大，上述时间复杂度不断增大，那么算法的执行效率越低。
例如：

int aFunc(void) {printf("Hello, World!\n");      // 需要执行 1 次return 0;                       // 需要执行 1 次
}

需要执行2次。

int aFunc(int n) {for(int i = 0; i<n; i++) {         // 需要执行 (n + 1) 次printf("Hello, World!\n");     // 需要执行 n 次}return 0;                          // 需要执行 1 次
}

需要执行n+1+n+1=2n+2次。
当n足够大时会将常数忽略。同理如果执行次数为n^3+n，次数足够大时会将n忽略。
如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))。
对于一个循环，假设循环体的时间复杂度为 O(n)，循环次数为 m，则这个循环的时间复杂度为 O(n×m)。

void aFunc(int n) {for(int i = 0; i < n; i++) {         // 循环次数为 nprintf("Hello, World!\n");       // 循环体时间复杂度为 O(1)}
}

在此式子中时间复杂度为 O(n × 1)，即 O(n)。
而对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c…，则这个循环的时间复杂度为O(n×a×b×c…)。分析的时候应该由里向外分析这些循环。

void aFunc(int n) {for(int i = 0; i < n; i++) {            // 循环次数为 nfor(int j = 0; j < n; j++) {        // 循环次数为 nprintf("Hello, World!\n");      // 循环体时间复杂度为 O(1)}}
}

此式子时间复杂度为 O(n × n × 1)，即 O(n^2)。
对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。例如时间复杂度为 max(O(n^2，O(n))时，取
O(n^2)。

然后便是二分，这在学Java基础的时候有一些接触，分为递归查找和非递归查找。
非递归二分查找：

public class Main {public static int binarySearch(int []a,int num){int len=a.length;int high=len-1;int low=0;while(low<=high){int mid=(high+low)>>1;if(a[mid]==num)return mid;else if(a[mid]<num)low=mid+1;elsehigh=mid-1;}return -1;}public static void main(String args[]){int []a={1,10,30,34,40,45,59};int index=Main1.binarySearch(a, 30);System.out.println(index);}
}

递归二分查找：

public class Main {public static int binarySearch_(int []a,int low, int high,int num){if(low<=high){int mid=(low+high)>>1;if(a[mid]==num)return mid;else if(a[mid]<num)low=mid+1;elsehigh=mid-1;return binarySearch_(a,low,high,num);}elsereturn -1;}public static void main(String args[]){int []a={1,10,28,36,42,45,76};int index=Main1.binarySearch_(a, 0,a.length-1,3);System.out.println(index);}
}

一道算法题：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int m = scanner.nextInt();int n = scanner.nextInt();int a[][]=new int[m][n];int sum=0;for (int i = 0;i<a.length;i++){for (int j = 0;j<a[0].length;j++){a[i][j]=scanner.nextInt();}}for (int i = 0;i<a.length;i++) {for (int j = 0; j < a[0].length; j++) {if (i==0||i==a.length-1){sum+=a[i][j];}else {sum += a[i][0];sum += a[i][a[0].length - 1];}}}System.out.println(sum);}
}

初接触算法，知识面还很浅，这周先做这些总结。

算法初接触1

算法第一弹
之前对算法接触的很少，没有一个明确的规划，也不太理解该学些什么，第一周就先简单总结一下吧。
算法中有算法复杂度，而算法复杂度又分为时间复杂度和空间复杂度：
①时间复杂度是指执行算法所需要的计算工作量。
②而空间复杂度是指执行这个算法所需要的内存空间。
时间复杂度一般与算法中执行次数成正比，一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。随着问题规模n的不断增大，上述时间复杂度不断增大，那么算法的执行效率越低。
例如：

int aFunc(void) {printf("Hello, World!\n");      // 需要执行 1 次return 0;                       // 需要执行 1 次
}

需要执行2次。

int aFunc(int n) {for(int i = 0; i<n; i++) {         // 需要执行 (n + 1) 次printf("Hello, World!\n");     // 需要执行 n 次}return 0;                          // 需要执行 1 次
}

需要执行n+1+n+1=2n+2次。
当n足够大时会将常数忽略。同理如果执行次数为n^3+n，次数足够大时会将n忽略。
如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))。
对于一个循环，假设循环体的时间复杂度为 O(n)，循环次数为 m，则这个循环的时间复杂度为 O(n×m)。

void aFunc(int n) {for(int i = 0; i < n; i++) {         // 循环次数为 nprintf("Hello, World!\n");       // 循环体时间复杂度为 O(1)}
}

在此式子中时间复杂度为 O(n × 1)，即 O(n)。
而对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c…，则这个循环的时间复杂度为O(n×a×b×c…)。分析的时候应该由里向外分析这些循环。

void aFunc(int n) {for(int i = 0; i < n; i++) {            // 循环次数为 nfor(int j = 0; j < n; j++) {        // 循环次数为 nprintf("Hello, World!\n");      // 循环体时间复杂度为 O(1)}}
}

此式子时间复杂度为 O(n × n × 1)，即 O(n^2)。
对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。例如时间复杂度为 max(O(n^2，O(n))时，取
O(n^2)。

然后便是二分，这在学Java基础的时候有一些接触，分为递归查找和非递归查找。
非递归二分查找：

public class Main {public static int binarySearch(int []a,int num){int len=a.length;int high=len-1;int low=0;while(low<=high){int mid=(high+low)>>1;if(a[mid]==num)return mid;else if(a[mid]<num)low=mid+1;elsehigh=mid-1;}return -1;}public static void main(String args[]){int []a={1,10,30,34,40,45,59};int index=Main1.binarySearch(a, 30);System.out.println(index);}
}

递归二分查找：

public class Main {public static int binarySearch_(int []a,int low, int high,int num){if(low<=high){int mid=(low+high)>>1;if(a[mid]==num)return mid;else if(a[mid]<num)low=mid+1;elsehigh=mid-1;return binarySearch_(a,low,high,num);}elsereturn -1;}public static void main(String args[]){int []a={1,10,28,36,42,45,76};int index=Main1.binarySearch_(a, 0,a.length-1,3);System.out.println(index);}
}

一道算法题：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int m = scanner.nextInt();int n = scanner.nextInt();int a[][]=new int[m][n];int sum=0;for (int i = 0;i<a.length;i++){for (int j = 0;j<a[0].length;j++){a[i][j]=scanner.nextInt();}}for (int i = 0;i<a.length;i++) {for (int j = 0; j < a[0].length; j++) {if (i==0||i==a.length-1){sum+=a[i][j];}else {sum += a[i][0];sum += a[i][a[0].length - 1];}}}System.out.println(sum);}
}

初接触算法，知识面还很浅，这周先做这些总结。