算法时间复杂度的大概计算方法
前言
最近在看看leetcode,很多题都要求时间复杂度在一定值之内。那么这个值该如何去计算呢?还是得捡捡基础知识。
时间复杂度
通俗点讲就是程序执行数据规模为N的算法所需要的大致时间,记作T(n)=O(f(n)),一般时间复杂度都叫O(n)。下面再引用一句牛逼点的话:
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数.记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度.数学语言表达就是:存在足够大的正整数M,使得T(n)≤M×f(n)。
计算方法
单位时间
假设有一个数据需要一行代码处理。
那么执行一行代码的时间为O(1),可以理解为单位时间。
N数量级数组
那么一个N长度的数组,就需要循环N次处理每一个数据,那么所需时间就是O(n)=单位时间*N,时间复杂度就是O(n)
N数量级二维数组
那么一个NN长度的二数组,就需要循环N次处理每一个数据,那么所需时间就是O(n)=单位时间N*N,时间复杂度就是O(n^2)。
其他复杂度计算
当然我们不只是遍历数组,可能是其他算法,比如二分查找。二分查找是每次取一半直到剩最后一个就是要找的数。
那么n个数总共需要k次二分来完成,因此每次次数除以2,n,n/2,n/4,…n/2^k
公式就是(进行过K次/2后只剩一个数):n/2^k=1
所以k=logn
所以所需时间就是O(n)=单位时间*logn,时间复杂度就是O(logn)。
总结
因此时间复杂度的计算方法可以以此类推来计算了,O(n)=单位时间*(n数据量下的执行次数)。
我们对常用算法的复杂度不要死记硬背,而是知道原理后,自然而然就能根据时间复杂度计算方法来计算出时间复杂度了。