所谓算法,其实就是我们用来操作数据、解决程序问题的一组方法。针对同一个问题,我们可以采用不同的算法,然后实现相同的结果。但是针对不同的算法,对于时间和资源的消耗却有不同的差别。而为了分析不同算法的效率,我们常常从 时间 和 空间 两个方面来对比,然后从中挑出最适合我们的解决方案。
本文主要从时间复杂度和空间复杂度的定义说起,然后介绍常见的时间复杂度和空间复杂度,最后则是对常见排序算法进行了总结。
总结起来,对于如何分析一段代码的时间复杂度,主要有如下 3 个实用方法:
void sayHello(String name){
System.out.prinln("Hello, " + String);
System.out.prinln("欢迎关注我的公众号:【村雨遥】");
}
int binarySearch(int[] arr, int target){
int left = 0;
int right = arr.length - 1;
while(left <= right){
int middle = left + (left - right) / 2;
if(arr[middle] == target){
return middle;
}else if(arr[middle] > target){
right = middle - 1;
}else {
left = middle + 1;
}
}
return -1;
}
int sum(int[] arr){
int total = 0;
for(int i = 0; i < arr.length; i++){
total += arr[i];
}
return total;
}
void hello (int n){
for( int i = 1 ; i < n ; i++){
int m = 1;
while( m < n ){
m *= 2;
}
}
}
void selectionSort(int[] arr, int n){
for(int i = 0; i < n; i++){
int min = i;
for(int j = i + 1; j < n; j++){
if(arr[j] < arr[min]){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
}
void demo(int n){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int k = 0; k < n; k++){
System.out.print("Hello, World");
}
System.out.print("------");
}
System.out.print("******");
}
}
int num1 = 1;
int num2 = 2;
int total = num1 + num2;
int[] arr = new int[n];
int[][] arr = new int[n][n];
对于面试中常见的的排序算法,以下总结给出了其时间复杂度以及空间复杂度,以及算法稳定性。
好了,以上就是今天文章的内容了。主要介绍了时间复杂度的定义、推导原则以及常见时间复杂度,还对空间复杂度定义以及常见空间复杂度进行了介绍,最后则是总结了常见排序算法的时间复杂度和空间复杂度。