专业版:算法的时间复杂度即算法的执行效率,即算法的执行时间与算法的输入值之间的关系。
通俗版:解决一个问题时,写出来的代码跑的时间越短越好。
O(1) < O(logN) < O(N) < O(NlogN) < O(n2) < O(2n) < O(n! )
一般情况下,我们计算时间复杂度主要是看有没有for循环和while循环,如果没有这两个循环的话一般执行的时间复杂度都是一个常量,即O(1)。
def O1(num): i = num j = num*2 return i+j从代码我们可以看出,无论num赋值多少,i=num;j=num*2;return i+j;三行代码执行时间不变,num不影响总的执行时间,总耗时是一个常数,即O(1),我们可以记为当num不影响执行次数时,时间复杂度为O(1)。
def test(num): total = 0 # 执行该语句的时间我们设为a for i in range(num): total += i # 执行该语句一次的时间为b return total # 执行该语句的时间我们设为c在计算最后的总耗时时,假设num=10,则total执行了10次total+i ,则第3,4行代码的执行时间为10b,最终整个test()函数的执行时间为a+10b+c,我们不难看出a,c的前面的数都是1且是不变的,而b前面的数随着num的赋值而改变,假设num=n,此时我们就忽略掉a,c而只看b,则执行时间为nb, 因为b是系数我们也将其忽略掉,最终的时间复杂度就为O(n)。
def Omn(num1,num2): total = 0 for i in range(num1): total += i for j in range(num2): total += j return total而如果此时有两个变量,且for循环和while循环的关系为并列,如第一个for循环的执行时间为m,第二个for循环的执行时间为n,因为两个循环是并列不相关的,所以最终时间复杂度为O(m+n)。
def On2(num): total =0 for i in range(num): for j in range(num): total += i+j而当两个for循环为嵌套关系,此时执行的时间为n*n,故而最终的时间复杂度为O(n2)。
而在一个for循环中,如,如果i是成倍的增加(i*2),则N在for循环中执行了logN次,这时代码执行的时间复杂度就为O(logN)。
def OlogN(num): i = 1 while (i<num): i = i * 2 return i
与O(n×n)即O(n2)同理,如果是for和while嵌套循环,其中一个为成倍增长,另一个做加法,则执行时间N*logN,最终的时间复杂度为O(NlogN)。
def ONlogN(num1,num2): total = 0 j =0 for i in range(num1): while (j < num2): total += i + j j = j * 2 return total