在平时开发当中,衡量一个程序设计执行的效率通常用大O函数表示法,下面依次从复杂度由低到高叙述下
O(1),最低复杂度。表示时间/空间的复杂度为固定的,与数据量大小没有关系。例如哈希算法,无论多少数据,通过一次计算便可以计算出对应的值,查找的复杂度为O(1)。一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行代码,它的执行复杂度也为O(1),因为执行的时间是固定的。
O(logn),表示数据量增大n倍后,执行的时间/空间增大logn倍。这里的log是以2为底的,比如,当数据增大256倍时,耗时只增大8倍。例如二分查找,256个数中最多8次便可以找到对应的数字。log也可以用3或者10为底,表示的复杂度依然为O(logn)。
O(nlogn),如果理解了上面的O(logn),如果我们执行了n遍的O(logn),那么复杂度就可以表示为O(nlogn)
O(n),表示时间/空间的复杂度随着数据量的增大而增大。例如遍历算法,遍历执行一个数组,或者遍历一个文件夹,他的执行时间/复杂度都随着数据量的增大而增大。
O(m➕n)、O(m✖️n),表示时间/空间复杂度取决于m、n两个数据量的值。
O(n^2),表示时间/空间的复杂度随着数据量的增大,复杂度也呈现出数据量的平方倍。例如执行一个冒泡排序算法。程序执行了数组长度*数组长度的执行复杂度变化。
O(n^3),表示时间/空间的复杂度随着数据量的增大,呈现出数据量的立方倍的增大。