算法
即存在输入输出,由有限步骤结束的程序.
因此,显而易见,算法并不是指一个单一的标准答案,而是一切能够完成要求的程序都可以称之为算法.但是算法之间根据性能的不同存在差异,评判这个差异的指标就是本篇分享的重点.
评判算法优劣的指标
1.时间复杂度
时间复杂度用O()表示,它的实质是算法的计算次数
这里先列举几个小例子
第一个例子
int n,ans=0; cin>>n; for(int i=0;i<n;i++){ ans++; } ans++; ans++; ans++; cout<<ans; 这段程序比较好理解,在这里,for循环中进行了n次运算,而之后对ans又进行了3次运算,在这里我们的有效计算次数为n+3.
但是这里需要注意时间复杂度并不是n+3,因为我们在实际操作时,n是会取到无穷大的,在这里n就是无穷,对于无穷来说,3就可以忽略不计,因此这段程序的时间复杂度为O(n).
再看一下第二个例子
int n,ans=0; cin>>n; for(int i=0;i<n;i+=2){ ans++; } cout<<ans; 这次不过多解释,有效计算次数为n/2,但因为n是趋于无穷的,所以时间复杂度仍然为O(n).
第三个例子
int n,ans=0; cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ ans++; } } for(int i=1;i<=n;i++){ ans++; } cout<<ans; 这次的代码有两个循环,第二个是n,第一个则是作为一个嵌套循环,比较容易得出经过了n*n次循环
这次的有效计算次数为n2+n,由于n趋向无穷,对n2来说,n可以忽略不计,所以这次的时间复杂度为O(n2).
最后一个例子
int arr[101]; int n; cin>>n; for(int i=0;i<n;i++) cin>>arr[i]; for(int i=n-1;i>0;i++){ for(int j=0;j<i;j++){ if(arr[j]>arr[j+1]){ swap(arr[j],arr[j+1]); } } } 这是一个冒泡排序算法,这次的有效计算次数为1+2+3+...+n-1,由等差数列的求和公式知道为(n2+n)/2.经过前面的例子,想必都知道了时间复杂度就是不带系数最高次项,这里就是O(n2)
经过上面的例子大家应该对算法的时间复杂度有了比较清晰的认识,这里我再补充几点
1.有限计算次数即没有n加入的程序,规定时间复杂度为O(1).
2.常见的时间复杂度有:O(1),O(logn),O(n),O(n2),O(n3).
2.空间复杂度
事实上在实际情况下,空间复杂度没有时间复杂度受重视,在实际学习中,大多数情况下是超过了运行时间,而不是超过规定内存.但它同样需要我们了解.
时空复杂度也用O()表示,它的实质是额外产生的空间.
int arr[101]; int n; cin>>n; for(int i=0;i<n;i++) cin>>arr[i]; int *arr=new int[n]; for(int i=n-1;i>0;i++){ for(int j=0;j<i;j++){ if(arr[j]>arr[j+1]){ swap(arr[j],arr[j+1]); } } } delete[]arr; 这里需要关注的是空间复杂度是额外产生的空间,因此初始的n个不计入空间复杂度,而之后的new出来的内存是空间复杂度,即为n,它的计算方法和时间复杂度一样,取不带系数的最高次项.
补充几点:
1.时间和空间往往是相对的.
2.常见的空间复杂度:O(1),O(n),O(logn*n)
3.稳定性
这里简单提一下,不过多赘述,后续会专门开一个新坑讲解一下.
