Java教程

【数据结构与算法】算法的时间复杂度

本文主要是介绍【数据结构与算法】算法的时间复杂度,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Python\数据结构与算法\算法\算法的时间复杂度

  • 1. 时间复杂度-概念
  • 2. 时间复杂度-常例分析
    • 2.1-时间复杂度-顺序表(越小用的时间越少,即越好)
    • 2.2-时间复杂度-O(1)
    • 2.3-时间复杂度-O(n)
    • 2.4-时间复杂度-O(m+n)
    • 2.5-时间复杂度-O(n^2^)
    • 2.6-时间复杂度-O(logN)
    • 2.7-时间复杂度-O(NlogN)

1. 时间复杂度-概念

专业版:算法的时间复杂度即算法的执行效率,即算法的执行时间与算法的输入值之间的关系。
  
通俗版:解决一个问题时,写出来的代码跑的时间越短越好

2. 时间复杂度-常例分析

2.1-时间复杂度-顺序表(越小用的时间越少,即越好)

O(1) < O(logN) < O(N) < O(NlogN) < O(n2) < O(2n) < O(n! )

2.2-时间复杂度-O(1)

  一般情况下,我们计算时间复杂度主要是看有没有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)。

2.3-时间复杂度-O(n)

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)

2.4-时间复杂度-O(m+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)

2.5-时间复杂度-O(n2)

def On2(num):
      total =0
      for i in range(num):
            for j in range(num):
                  total += i+j

  而当两个for循环为嵌套关系,此时执行的时间为n*n,故而最终的时间复杂度为O(n2)

2.6-时间复杂度-O(logN)

  而在一个for循环中,如,如果i是成倍的增加(i*2),则N在for循环中执行了logN次,这时代码执行的时间复杂度就为O(logN)

def OlogN(num):
      i = 1
      while (i<num):
             i = i * 2
       return i

2.7-时间复杂度-O(NlogN)

与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
这篇关于【数据结构与算法】算法的时间复杂度的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!