常见函数的时间复杂度

【list】的内置函数时间复杂度
方法 复杂度 简介
index[x] O(1) 索引
index assignment O(1) 索引赋值
append O(1) 尾部追加
pop() O(1) 尾部弹出
pop(i) O(n) 指定位置弹出 n列表长度, 最坏时间复杂度
insert(i, item) O(n) 指定位置添加
del operator O(n) 删除, 代表一个一个元素去清空
iteration O(n) 迭代
contains(in) O(n) 看谁是否在列表中, 需要遍历
get slice[x:y] O(k) 取切片, 从x取到y, 一次定位到x, 然后取到y ,x和y之间有多少就是k
del slice O(n) 删除切片 删除位置之后, 后面的元素都需要往前移动
set slice O(k) 设置切片, li[0:3] = [1, 2, 3, 4]k是补充的东西数量
reverse O(n) 置返
concatenate O(k) 代表使用的+, 把两个列表加到一起, k是第二个列表中的元素
sort O(nlogn) 排序
multiply O(nk) 相乘 li=[1, 2] -> n li * 10 -> k

【dict】 的内置函数时间复杂度
方法 复杂度 简介
copy O(n) 复制
get item O(1)
set item O(1) 设置
delete item O(1) 删除键
contains(in) O(1) 包含
iteration O(n) 迭代

原文地址:https://www.cnblogs.com/zhongmin/p/11011089.html

时间: 06-12

常见函数的时间复杂度的相关文章

在O(n)时间复杂度内找到出现超过一半的数

#include<iostream> using namespace std; bool solver(const int a[],const int n, int & num) { if(NULL == a || 0>= n) return false; ////注意,是小写~ int count = 0; int com = a[0]; for(int i = 1;i<n;i++) { if(0 == count) { com = a[i]; count++; } el

数据结构——时间复杂度

分析算法的时间复杂度: 算法的时间复杂度就是反应了程序执行时间随着输入规模增长而增长的量级,这个标准可以很好的反映出算法的优劣性质. 算法的频度: 一个算法执行所耗费的时间完全可以以程序执行的次数进行估算,程序执行的次数越多,时间复杂度也就越复杂,也就是说算法花费的时间与算法中语句执行的次数成正比例,因此,一个算法中语句执行的次数可以叫做时间频度.记为T(n). 时间复杂度: 由于n表示规模,当n不断变化的时候,T(n)也会随之不断变化,当我们需要知道他的变化趋势的时候,就要引入时间复杂度.一般

如何计算时间复杂度

本文是转载的,原作者不详. 一.概念 时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数) 比如:一般总运算次数表达式类似于这样: a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f a ! =0时,时间复杂度就是O(2^n); a=0,b<>0 =>O(n^3); a,b=0,c<>0 =>O(n^2)依此类推 eg: (1) for(i=1;i<=n;i++) //循环了n*n次,当然是O(n^2) for(j=1;j<=

leetcode链表--13、median-of-two-sorted-arrays(两个排序数组的中位数,时间复杂度)

题目描述 There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). 题目解析:本题关键之处在于时间复杂度要求为O(log(m+n)),本题如果采用合并并排序两数组的方式,时间复杂度为O((m+n)*log(n+m))但是在牛客网上

时间复杂度

一概念 时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数) 比如:一般总运算次数表达式类似于这样: a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f a ! =0时,时间复杂度就是O(2^n); a=0,b<>0 =>O(n^3); a,b=0,c<>0 =>O(n^2)依此类推 二.计算方法 1.一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道.但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花

统计数组[1-n]中各个元素出现的次数,时间复杂度O(n),空间复杂度O(1),可改变数组结构

* 统计数组中每个元素出现的次数 * 数组长度为N,每个元素范围为[1,N]. * 统计各个元素出现的次数,要求时间复杂度为O(N),空间复杂度为O(1).可以修改数组中元素的值. * * 思路:遍历到每一个元素,将该(元素值 - 1)作为下标值,将该下标的元素赋值(若为正,赋值-1:若为负值,-1) * 最后,每个下标中存储的元素即为统计次数,而下标+1即为元素值. 代码: public static void main(String[] args) { // TODO Auto-genera

算法 笔记1 时间复杂度计算

评价一个算法的优劣应该从三个方面判断 1.时间复杂度 : 执行算法所耗费的时间,即时间复杂度 2.空间复杂度 : 执行算法所耗费的存储空间,主要是辅助空间 3.可读性和可操作性 : 算法应当易于理解,易于编程,易于调试等 时间复杂度 一般情况下,将算法所要求求解问题的输入量称为问题的规模,并用一个正整数n来表示 T(n)就是该算法的时间耗费,他是该算法所求问题规模n的函数 算法中基本操作重复执行的次数时问题规模n的某个函数f(n) 算法的时间量度记为: T(n) = O(F(n)) 时间复杂度的

异或的应用场景:以O(N)时间复杂度查找文章中出现了奇数次的字符串

有个500g大小的文件,程序的运行内存1g,这个文件里边每行一个单词. 正常情况下,每个单词出现的次数为偶数次: 但是,由于程序出现bug,有一个单词出现了奇数次,怎么找到这个单词? import com.google.common.base.Splitter; import org.apache.commons.lang.RandomStringUtils; import java.util.List; /** * Created by kongzheng on 16/3/31. */ pub

算法的时间复杂度和空间复杂度

<算法的时间复杂度和空间复杂度合称为算法的复杂度> --->算法的时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道.但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了.并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多.一个算法中的语句执行次数称为语句频度或时间频度.记为T(n). (2)时间复杂度 在刚才提到的时间频度中,n称为问题的规模

算法时间复杂度和空间复杂度详解

算法的时间复杂度和空间复杂度合称为算法的复杂度. 1.时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道.但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了.并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多.一个算法中的语句执行次数称为语句频度或时间频度.记为T(n). (2)时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时