Python算法笔记（1）-时间复杂度、空间复杂度

Python算法笔记（1）-时间复杂度

1.时间复杂度

时间复杂度是一个描述算法的运行时间的一个函数，它描述了算法的运行时间和输入数据的规模之间的关系，时间复杂度的表示方法用O表示，时间复杂度也用来考察输入值无限趋近无穷时的情况。

一：常量阶 O(1)

当执行次数为n时表示常量阶

def person(n):
    print("有%d个人" % n)
if __name__ == '__main__':
    person(3)

二：对数阶 O(logn)

当执行5logn次数是对数计算时

def person(n):
    while n>1:
        print("有%d个人" % n)
        print("他们都走了")
        n /= 2
if __name__ == '__main__':
    person(10)

三：线性阶 O(n)

3n次计算时是线性

def person(n):
    for i in range(n):
        print("有%d个人" % n)
        print("他们都走了")
if __name__ == '__main__':
    person(2)

四：线性对数阶 O(nlogn)

def person(n):
        while n > 1:
            print("有%d个人" % n)
            print("他们都走了")
            n*(n/2)

if __name__ == '__main__':
    person(2)

五：n方阶 O(nⁿ)

def person(n):
        for i in range(1,n):
            print("有%d个人" % n)
            print("他们都走了")
            NP = n**n
            print("n方阶是%d" %NP)

if __name__ == '__main__':
    person(2)

六：指数阶 O(2ⁿ)

def person(n):
        for i in range(1,n):
            print("有%d个人" % n)
            print("他们都走了")
            NP = 2**n
            print("n指数阶是%d" %NP)

if __name__ == '__main__':
    person(3)

七：阶乘阶 O(n!)

def person(n):
        res = 1
        for i in range(1,n+1):
            res *=i
            print("n阶乘阶是%d" %res)

if __name__ == '__main__':
    person(3)
    

当满足公式下的运行下，当n的增加时，运行效率在指数阶和阶乘阶的运行效率会变得非常低，所以需要合理选择一个计算方式，而运行速度来看：常量阶<对数阶<线性阶<n方阶

2.空间复杂度

空间复杂度是算法在运行时间复杂度算法时所占用的空间大小的度量，一般用S(n)表示。

一：常量空间

没有特殊标记O(n),跟输入规模没有直接的关系。

def ex(n):
	i = 3

二：线性空间

O(n)，集合大小和输入规模n成正比

def ex(n):
	ar = [[0]*n]

三：二维空间

当算法分配一个空间是二维列表集合时，长度与宽度输入规模成正比，O(n2次方)

def ex(n):
	ar = [[0]*n]*n

四：递归空间

当计算机运行程序时会调用相应的内存来存储，也就有了出栈和入栈的行为，当函数返回时，信息就会从栈中出来

def ex(n):
	if n>>0:
		ar(n-1)