1、时间复杂度

首先,时间复杂度并不是指程序具体的运行时间,而是算法执行语句的次数。当有多个算法解决同一个问题时,我们可以通过计算时间复杂度来决定选择哪一个算法。

常见的时间复杂度有:常数阶O(1)、对数阶O(log2 n)、线性阶O(n)、线性对数阶O(n log2 n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n),随着n的不断增大,时间复杂度不断增大,算法花费的时间也就越多。

计算方法:

1、选取相对增长最高的项

2、最高项系数化为1

3、若是常数的话用O(1)表示

如f(n) = 2*n^3+2n+100,则O(n) = n^3。

通常我们计算时间复杂度都是按最坏情况来计算的。

(1)如果算法执行时间不随问题规模n的增加而增加,即使算法中语句再多,执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

x = 1
while x < 10:
    x += 1
    print(x)

该算法执行次数是10,如果把x<10换成x<10000,也不过是执行10000次,仍然是一个常数,时间复杂度为O(1)。

(2)当有若干个循环语句时,算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的

x = 1
for i in range(1, n):
    for j in range(1, n):
        x += 1

该算法中,外层for循环每执行一次,内层for循环都要执行n次,执行次数是根据n决定的,时间复杂度为O(n^2)。

(3)循环不仅与n有关,还与执行循环所满足的条件有关

x = 1
while x < n and list[x] != 1:
    x += 1

该算法中,如果list[x]不等于1的话,时间复杂度是O(n),如果等于1的话,时间复杂度是0。

2、空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量。

计算方法:

1、忽略常数,用O(1)表示

2、递归算法的空间复杂度 = 递归深度N*每次递归所需要的辅助空间

3、对于单线程来说,递归运行时的堆栈,求的是递归最深的那一次压栈所耗费的空间的个数,因为递归最深的一次所耗费的空间足以容纳所有的递归过程
a, b, c = 3, 4, 5
print(a, b, c)

空间复杂度为O(1)。

def fun(n):
    k = 10
    if n == k:
        return n
    else:
    n += 1
    return fun(n)

递归实现,调用fun函数,每次都创建1个变量k,调用n次,空间复杂度为O(n)。

3、举个栗子

接下来我们分析一下常见的顺序查找、二分查找、冒泡排序的时间复杂度和空间复杂度。

(1)顺序查找
def seq_search(l, data):
        length = len(l)
        for x in range(0, length-1):
            if l[x] == data:
                return f'{data}是list中第{x+1}个数'
        return 'list中没有这个数'

顺序查找的语句执行次数和数组中元素的顺序有关,如果查找的数在第一个,则执行一次就结束了,如果在最后一个,则需要执行n次(假设数组有n个元素),那么时间复杂度为(1+2+…+n)/n = (n+n^2)/2,则时间复杂度为O(n),由于不需要辅助空间,空间复杂度为O(1)。

(2)二分查找
def binary_search(l, data):
        length = len(l)
        first = 0
        last = length - 1
        while first <= last:
            mid = (int)((first + last) / 2)
            if l[mid] > data:
                last = mid - 1
            elif l[mid] < data:
                first = mid + 1
            else:
                return f'{data}是list中第{mid+1}个数'
        return 'list中没有这个数'

二分查找的前提条件是数组有序,每次执行完毕后,查找范围缩小一半,即n, n/2, n/4, n/(2^k),由于n/(2^k)取整后>=1,即令n/(2^k)=1,可得k=(log2 n),则时间复杂度为O(log2 n),由于不需要辅助空间,空间复杂度为O(1)。

(3)冒泡排序
def bubble_sort(l):
        length = len(l)
        # 序列长度为length,需要执行length-1轮交换
        for x in range(1, length):
        # 对于每一轮交换,都将序列中的左右元素进行比较
        # 每轮交换当中,由于序列最后的元素一定是最大的,
        # 因此每轮循环到序列未排序的位置即可
            for i in range(0, length-x):
                if l[i] > l[i + 1]:
                    temp = l[i]
                    l[i] = l[i+1]
                    l[i+1] = temp

冒泡排序有两层for循环,一般来说,对于for循环,可视为一层for循环时间复杂度为O(n),两层为O(n^2),以此类推,参考时间复杂度第二点,所以,冒泡排序时间复杂度为O(n^2),需要开辟一个临时变量空间temp来辅助,为常数,空间复杂度为O(1)。

分类: 算法

发表评论

电子邮件地址不会被公开。