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(n²) < O(2ⁿ) < 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(n²)

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

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

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