1243

时空复杂度

T=O(n)

T时间复杂度 O()函数 n数据量

时间复杂度是用来[估算]代码的基本操作的执行次数的函数

基本操作：通常指循环中的内层代码

for(.....){

   cout<<i;//内层代码

}

for(i:0~n)

   for(j:0~m)

       if(i+j>0) cout<<i<<j;//内层代码

冒泡排序时间复杂度：

n+n-1+n-2+...+1=n(n+1)/2

当n非常大的时候n(n+1)/2无限接近于n^2，所以冒泡的时间复杂度是O(n^2)

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^x)<O(n!)

时间复杂度的作用：

1、估算程序是否超时（10000000）

2、优化代码

空间复杂度：

程序内存占用的空间（创建变量占用的空间）

通过算法解题额外占用的内容空间

百练：回文素数

下节课栈