算法学习笔记一、时空复杂度

wuyumin 发布于2019-08-16 11:08 / 1860人阅读

摘要：动态规划背包士兵路径复杂度谈算法一定要考虑复杂度时间复杂度和空间复杂度时间复杂度计算机基本操作的次数汇编指令的条数寻址跳转空间复杂度所需占用的内存字节数两者区别空间是可以返回利用的。

面试求职班一笔记

算法主要研究：时空复杂度

算法的特征：

有穷性，

确定性，

可行性，

可能没有输入，但一定有输出

常用算法

穷举法（eg：求N个数的全排列；8皇后问题）

减而治之（二分查找——减而治之；归并排序——分而治之）

贪心算法（最小生成树；单源最短路）所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

动态规划（背包；士兵路径）

复杂度

谈算法一定要考虑复杂度

时间复杂度和空间复杂度

时间复杂度：计算机基本操作的次数（汇编指令的条数）+ - * / % 寻址跳转

空间复杂度：所需占用的内存字节数

两者区别：空间是可以返回利用的。

表示方法：O(n) 忽略常数（高阶无穷小）注意：算法复杂度是考虑算法最坏情况时的复杂度

eg: 快速排序的复杂度 O(n^2)，这个就是他的最坏情况

常见的复杂度

O(1): 基本运算 + - * / % 寻址跳转

O(logN): 二分查找

O(N^(1/2)): 枚举约数

O(N): 线性查找

O(N^2): 朴素最近带你对

O(N^3): Floyd最短路；普通矩阵乘法

O(NlogN): 归并排序；快速排序的期望复杂度；基于比较排序的算法下界

$$a_1,a_2,...a_n 排序全排列的时间复杂度为 n!$$
$$ 当 a_i< a_j时$$
$$复杂度变为: frac{n!}{2}$$
$$当有k个关系时，每次都能排除一般的可能$$
$$复杂度为: frac{n!}{2^k}$$
$$令: frac{n!}{2^k} = 1 即 n!=2^k$$
$$k=log_{2}{n!} < log_{2}{n^n}=nlog_{2}{n}=nfrac{log n}{log2}< nlog{n}$$
以上为推导过程

        8. O($2^N$): 枚举全部的子集   注意：一个集合全部子集的数量是2^N
        9. O($N!$): 枚举全部排列

总结:

优秀算法排序：

$$O(1) < O(log{n}) < O(sqrt{n} < O(n) < O(nlog{n}))$$

可以优化的：

$$O(n^2)< O(n^3)< O(2^n)< O(n!)$$

算法估计，计算机1s能运算1亿条指令，注意以下数字

$$(1000)^2=1亿; (465)^3=100,544,625; 12!=479001600$$

常用的时间复杂度分析方法

    1. 输入输出
        1. N个数组求和，时间复杂度下限为: O(n)
        2. 输出全排列的复杂度在O(n!)以上
    2. 循环次数
        eg: 循环嵌套的复杂度至少是O(n^2)
        for(i...n)
            for(i...n)
    
    3. 均摊分析法
        多个操作一起计算时间复杂度
        eg1: MULTIPOP的队列，可以一次性出队k个元素，但每个元素出入队列只能有一次
        eg2: 动态数据尾部插入操作（C++中是vector，java中是ArrayList）
        一旦元素超过容量限制，则重新扩大并分配空间，将旧数据复制到新的内存地址上。
        有空间的情况下复杂度是O(1)
        空间满了再扩大的时候的复杂度是O(n)
        重新分配k次的复杂度是O(2^n)

$$O(1)+O(2)+O(4)+...+O(2^n)=O(2^n-1)$$

GPU云服务器云服务器学习笔记一算法复杂度最大流算法时间复杂度最短路径算法复杂度

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71032.html

笔记｜缓存

摘要：缓存算法我是，我会统计每一个缓存数据的使用频率，我会把使用最少的缓存替换出缓存区。浏览器就是使用了我作为缓存算法。在缓存系统中找出最少最近的对象是需要较高的时空成本。再来一次机会的缓存算法，是对的优化。直到新的缓存对象被放入。缓存什么是缓存？ showImg(https://segmentfault.com/img/bVusZg); 存贮数据（使用频繁的数据）的临时地方，因为取原始...

elliott_hu 2019-08-06 13:15 评论0 收藏0
WebGL three.js学习笔记使用粒子系统模拟时空隧道（虫洞）

摘要：学习笔记使用粒子系统模拟时空隧道本例的运行结果如图时空隧道演示地址的粒子系统的粒子系统主要是依靠精灵体来创建的，要实现中的粒子系统创建，一般有两种方式。 WebGL three.js学习笔记使用粒子系统模拟时空隧道本例的运行结果如图：showImg(https://img-blog.csdnimg.cn/20190426222855492.png?x-oss-process=ima...

Guakin_Huang 2019-08-23 17:10 评论0 收藏0
深度学习的时间序列模型评价

摘要：技术总言这次主要说最近发展的无监督特征学习和深入学习，其对于时间序列模型问题的评价。建模连续数据的传统方法包括从假定时间序列模型参数的估计，如自回归模型和线性动力系统，和著名的隐马尔可夫模型。此外，时间序列对时间变量有明显依赖性。技术总言：这次主要说最近发展的无监督特征学习和深入学习，其对于时间序列模型问题的评价。这些技术已经展现了希望对于建模静态数据，如计算机视觉，把它们应用到时间序列数...

zhaochunqi 2019-04-25 18:13 评论0 收藏0
【数据结构(C语言描述)】时空复杂度

摘要：目录一时间复杂度例题二空间复杂度例题三常见复杂度对比一时间复杂度时间复杂度一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数。找到某条基本语句与问题规模之间的数学表达式，就是算出了该算法的时间复杂度。 ...

Y3G 2021-10-12 10:12 评论0 收藏0