企业网站关键字优化,企业网站制作公司排名,网站开发毕设需求分析,辽宁招标工程信息网今日复习内容#xff1a;基础算法中的时间复杂度
时间复杂度分析
时间复杂度是衡量算法执行时间随输入规模增长的增长率。通过分析算法中基本操作的执行次数来确定时间复杂度‘常见的时间复杂度包括#xff1a;常数时间O(1)#xff0c;线性时间O(n),对数时间O(log n)…今日复习内容基础算法中的时间复杂度
时间复杂度分析
时间复杂度是衡量算法执行时间随输入规模增长的增长率。通过分析算法中基本操作的执行次数来确定时间复杂度‘常见的时间复杂度包括常数时间O(1)线性时间O(n),对数时间O(log n)平方时间O(n^2)等。在计算的时候我们关注的是复杂度的数量级并不要求严格的表达式 一般我们关注的是最坏时间复杂度用O(f(n) )表示大多数时候我们仅需估算即可一般来说评测机1秒大约可以跑2e8次运算我们要尽可能地让我们的程序运算规模的数量级控制在1e8以内。时间复杂度O(x)x为程序运行计算次数只考虑如果同时存在多项仅考虑最高项 1 O(n^2 n) O(n^2) (2) O(n 5) O(n) (3) O(n^3 n 10) O(n^3) 第一个例子
我只是用它来计算没有运算结果
n int(input())
a list(map(int,input().split()))
tot 0
for i in range(n):tot a[i]
print(tot)
这个题的时间复杂度是O(n) 。
接下来我来讲一下过程结合我写的代码
第一行时间复杂度为O(1)
第二行时间复杂度为O(n)
第三行时间复杂度为O(1)
第四,五行循环体):时间复杂度为O(n)
第六行时间复杂度为O(1)。
所以目前它的时间复杂度为O(2n3)
简单来说就是读入数据数据量为n的那行和循环体循环次数是n的时间复杂度是n别的都以1来计算。
然后上面讲过一个式子O(kn k1) O(n)这里的k和k1都是常数
所以这个题的最终时间复杂度是O(n)。 第二个例子 n int(input())
a list(map(int,input().split()))
tot 0
for i in range(n):for j in range(n):tot a[i]*a[j]
print(tot)
这个题的时间复杂度为O(n^2) 。
同样我来解释一下
第一行时间复杂度为O(1);
第二行时间复杂度为O(n);
第三行时间复杂度为O(1);
接下来的三行嵌套循环体时间复杂度为O(n*n)
最后一行时间复杂度为O(1)。
所以它目前的时间复杂度为O(n^2 n 3)然后上面有一个式子O(k*n^3 k1*n 10) O(n^3)k和k1是常数时间复杂度存在多项的情况下取最高项所以这个题最终的时间复杂度是O(n^2)。 第三个例子
n int(input())
a list(map(int,input().split()))
tot 0
for i in range(n):for j in range(i,n):tot a[i]*a[j]
print(tot)
这个题和上一个的区别是循环体的内循环初始值变了。
以下是过程
第一行时间复杂度为O(1);
第二行时间复杂度为O(n);
第三行时间复杂度为O(1);
接下来的三行嵌套循环体单独分析一下内容
外循环i 1内循环执行n-1次
外循环i 2内循环执行n-2次
......
外循环i n-1内循环执行1次
所以它的总时间复杂度为O((1n-1)*n/2)即O(n*n/2)。 最后一行时间复杂度为O(1)。
所以加起来它的时间复杂度为O(n*n/2 n 3)还是用上面的公式所以它最终的时间复杂度为O(n^2)。 第四个例子
n int(input())
a list(map(int,input().split()))
tot 0
for i in range(n):for j in range(0,n,i):tot a[i]*a[j]
print(tot)
这个题与第三个题的区别是取值步长不同。分析方法一样。 我再重复一遍过程但区别很小。
第一行时间复杂度为O(1);
第二行时间复杂度为O(n);
第三行时间复杂度为O(1);
接下来的三行嵌套循环体单独分析一下内容
外循环i 1内循环执行n次
外循环i 2内循环执行n/2次
......
外循环i n内循环执行n/n次
所以它的时间复杂度为O(n n/2 n/3 n/4 ...... n/n) O(nlog(n))这是调和级数 归并排序时间复杂度
T(n)记为n个元素的排序时间归并排序先把n的问题分解成两个n/2的问题然后把两个有序list合并。 1先把n的问题分解成两个n/2的问题T(n/2)*2 (2) 然后把两个有序list合并,On
具体推导过程 T(n) 2T(n/2) O(n); T(n/2) 2T(n/4) O(n/2) ; 带回 T(n) 4T(n/4) O(n) O(n); T(n) 8T(n/2) O(n) O(n) O(n) O(nlog(n)); OK今天先写到这里后续我会补充几个例题下次继续期末考还没结束累死了
