on是什么意思（1）、把输⼊规模看成x轴，所花时间/空间看成y轴
O（n）就是y=x，y随x的增长⽽线性增长。也就是成正⽐，⼀条斜线。
O（1）就是y=1，是⼀个常量，不管x怎么变，y不变，⼀条与x轴平⾏的线。
（2）、举个简单的例⼦，要从0加到n，我们会这么写：
int sum = 0;
for(int i = 0;i<=n;++i) {
sum + = i;
}
⼀共算了n次加法，那么就说这个时间复杂度是O（n）。当然O（n）的精确的概念是，是n的最⾼次⽅，⽐如，某个计算共计算了3n+2次，那么这个时间复杂度也是O（n），因为3n+2中的最⾼次⽅是n。
如果代码这么写：
int sum = 0;
for(int i = 0;i<= n;i++) {
for(int j = 0;j<= n;j++) {
sum + = (i + j);
}
}
很明显⼀共算了n^2次加法，那么就说这个时间复杂度是O（n^2），和这个上⾯的类似，如果某个算法计算了3*n^2+n+1次，其时间复杂度仍然是O（n^2），因为3*n^2+n+1中的最⾼的次⽅是n^2，所谓O1就是计算的次数是常量，我们还以上⾯从0到n的例⼦来说，如果我们⽤等差数列的公式，那么，代码可以这么写：
int sum = n*(n+1)/2
不管n有多⼤（当然不能溢出了），通过上⾯的公式只需要计算⼀次，也就是说计算的次数是不变的，这种情况的时间复杂度就可以说成
O（1），再⽐如这个计算，不管其他条件如何变化，均只计算5次就能计算出结果，那么这种情况就是时间复杂度，也就是O（1）。（3）、
要在hash表中到⼀个元素就是O（1）
要在⽆序数组中到⼀个元素就是O（n）
访问数组的第n个元素是O（1）
访问链表的第n个元素是O（n）
也就是说：
如果实现中没有循环就是O（1）
如果实现中有⼀个循环就是O（n）
（4）、算法复杂度：算法复杂度分为时间时间复杂度和空间复杂度。其作⽤是：时间复杂度是度量算法执⾏时间的长短；⽽空间复杂度是指算法所需存储空间的⼤⼩。
发布评论