NLP(2) 算法复杂度,归并排序,主成分分析,斐波那契数列的复杂度

1411-李同学

发表文章数:148

首页 » 算法 » 正文

第二节:算法复杂度

1、引入

  • 时间复杂度
  • 空间复杂度
    O(N)😮 Notation
int a=0,b=0;
for (i=0; i<N ; i++)
	a=a+rand(); #N*一个操作
	b=b+rand(); #N*一个操作
for (j=0; j<N/2;j++)
	b=b+rand();#N/2*一个操作

时间复杂度:o(N)
空间复杂度:两个单位的内存空间O(1)

int a=0;
for (i=0;i<N;i++){
	for (j=N;j>i;j--){
		a=a+i+j;
	}
}

时间复杂度O(N^2)
空间复杂度O(1)

int a=0,i=N;
while(i>0){
	a+=i;
	i/=2;
}

时间复杂度O(logn)

我们每当说算法x的效率要高于y时是指?

x的时间复杂度小于y

定理

如果x的时间复杂度要优于y的时间复杂度,只有N足够大时,可以保证x的实际效率要优于y的实际效率吧

常见复杂度排序

O(1)<O(log n)<O(n)<O(nlogn)<O(n^ 2) < O(n^ 3 ) < O(2^n)

2、归并排序 Merge sort

算法种类:divide and conquer
A=[3,4,1,6,7,2,5,9]
目标:sort(A)

NLP(2) 算法复杂度,归并排序,主成分分析,斐波那契数列的复杂度

3、Master Theorem——主方法分析

适用于:
NLP(2) 算法复杂度,归并排序,主成分分析,斐波那契数列的复杂度
NLP(2) 算法复杂度,归并排序,主成分分析,斐波那契数列的复杂度
NLP(2) 算法复杂度,归并排序,主成分分析,斐波那契数列的复杂度
对于a=b=2,f(n)=n时,时间复杂度为O(nlogn)
NLP(2) 算法复杂度,归并排序,主成分分析,斐波那契数列的复杂度
手写笔记
NLP(2) 算法复杂度,归并排序,主成分分析,斐波那契数列的复杂度

k为logn函数的指数项

4、斐波那契数的时间复杂度

序列依次为1,1,2,3,5,8,13,21,…
问题:怎么求出序列中第n个数

def fib(n):
    if n <3:
        return 1
    return fib(n-2)+fib(n-1)
print(fib(3))

NLP(2) 算法复杂度,归并排序,主成分分析,斐波那契数列的复杂度
时间复杂度:看需要把f(8)不算分解,分解到几层,到最低层需要

2

n

2^n

2n的操作。

计算空间复杂度:O(N)

NLP(2) 算法复杂度,归并排序,主成分分析,斐波那契数列的复杂度
简化算法:
dynamic programming,复用前向计算过的数值

import  numpy as np
def fib(n):
    tmp=np.zeros(n)
    tmp[0]=1
    tmp[1]=1
    for i in range(2,n):
        tmp[i]=tmp[i-2]+tmp[i-1]

    return tmp[n-1]

通过移动指针计算

def fib2(n):
    a,b=1,1
    c=0
    for i in range(2,n):
        c=a+b
        a=b
        b=c
    return c

未经允许不得转载:作者:1411-李同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《NLP(2) 算法复杂度,归并排序,主成分分析,斐波那契数列的复杂度》 发布于2021-02-06

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录