【算法】时间复杂度big O
2021-04-14 12:26
标签：就是 理解 个数 第一个 大小 时间复杂度 数字 理论 算法 首先，评论一个算法的时间复杂度，都是讲的最差值，比如我有一个数组a=[3,2,1,4,5]需要排序，那算法的时间复杂度是按[5,4,3,2,1]这样子的来排序所需的时间来计算的（怎么理解呢，就是，我数组如果是[1,2,3,4,5]，算法直接不需要排序，已经有结果了，那肯定跟我要排序[5,4,3,2,1]所需要的时间是不同的，[5,4,3,2,1]这样子的是每个数字都要计算一下位置） ①现在已知一个数组a，里面有5个值，a=[1,2,3,4,5] 假如：取a[2]需要1秒 那么：随着a的扩大，比如a有10万个元素,a=[1,2,3，...100000]，取a[10000]也需要差不多1秒（因为取数组的值只是计算一个偏移量就可以取到了） 对于取这个数组某个位置的值，不取决于这个数组的大小，所执行的时间都是1秒 对于“取这个数组某个位置的值”这个操作来说，时间复杂度是一个常数 所以，时间复杂度为O(1) ②已知一个链表a，有10个数 假如：取最后一个值需要1秒 那么：理论上，如果链表a有100个数，那么取最后一个值需要10秒（因为链表需要从第一个值开始一直往下取值） 对于取这个链表上最后一个位置的值，取决于这个链表的规模，当链表扩大（扩大到N），所需要的时间也在增加， 所以，时间复杂度为O(n) 还有其他的，比如一个算法需要对一个数组进行两遍循环，那么他的时间复杂度则为O(n²) 【算法】时间复杂度big O 标签：就是 理解 个数 第一个 大小 时间复杂度 数字 理论 算法 原文地址：https://www.cnblogs.com/fengzx120/p/13337195.html
下一篇：排序算法整理