算法温习

参加工作已经4年,最近跳槽一看算法,基本上忘干净了,又找个教程温习一下,随手记一点笔记方便之后使用

关于为什么要学习算法

再次学习算法,对为什么要学习算法有了一些深层次的理解。

狭义的讲,学习算法其本质是学习并熟悉背后的常用模式,工作中遇到问题可以去尝试套用这些模式。因为遇到一个基础问题,想要短时间自己去从0去设计一个新的模式,同时性能还要非常优秀,几乎是不可能的。

广义的讲,是学习计算机的编程思维。能解决问题的逻辑抽象有很多种,但是有的是易于用编程实现的,譬如回溯算法,就能够用递归非常容易的实现,算法可以帮助我们习惯从代码实现的角度去思考一个问题。

基础

常数操作

与数据量无关的操作,统计时间复杂度的基本单位;当然不同的常数操作时间有所差别,譬如乘法和按位与;

时间复杂度

常数操作的数量,通常表示为:O(高阶项)

时间复杂度只是估计值,最好的测量方式是实际运行来比较运行时间。

  1. 平均
  2. 最好
  3. 最坏

空间复杂度

需要的额外辅助空间;O(1)指只是需要常数数量的额外空间

位运算

与/或/非/异或 操作是提取某些位的重要方法

不需要额外空间实现数组交换

有一种取巧的方式通过异或运算(^):相同为0,不同为1

不过只能在数组指向不同对象时使用,否则会清零。

异或满足交换律和结合律

a^a=0; 0^a=a;

异或这个特征可以用在一些算法之中

对数器

通过随机样本产生器产生数据,然后检测某一个优化算法和已知正确的算法的结果是否一致;大量的测试可以

递归操作

当一个问题可以被拆解成相同子问题,且当其规模小到一定程度时就可以得到解决(边界),就可以采用递归操作处理;

java里面递归实现的基础是:栈帧

递归操作的时间复杂度可以用master公式来求,比较复杂。

排序算法

十大经典排序算法:https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

选择排序

O(n^2), O(1)

冒泡排序

O(n^2), O(1)

插入排序 

插入排序和选择排序,冒泡排序的时间复杂度有一个区别,数据状况会影响它常数操作的总数,也就是影响时间复杂度估算。

最坏情况时间复杂度:O(n^2)

最好情况是:O(n)

通常定义时间复杂度是按照最差情况来计算O(n^2)

归并排序

利用了递归的思想

时间复杂度三个都是O(N*logN)

空间复杂度O(N)

归并排序为什么时间性能比前三者好因为前三个排序有大量的比较而很多比较关系在使用之后就被抛弃了这样就出现了浪费有效利用这些关系避免重复比较就能提升性能。   

归并变形数组小和问题

数组中左边比当前数小的数累加叫数组的小和。[1,3,4,2,5] -> 16

得出O(N*logN)复杂度的计算方法

类似:逆序对问题。

快速排序

1.0算法以最后一个数作为标准,大于的放前面,小于的放后面。然后递归这个过程。

2.0算法:1.0基础上,对等值区域避免排序

3.0算法:划分值如果很居中则算法时间复杂度较低;故随机选一个数作为标准

时间复杂度最坏O(n^2),最好/平均:O(nlogn):好情况每次递归都平分数组,一共需要递归logn次,每次需要n时间,复杂度为O(n*logn),最坏情况每次都把数组分成1和n-1,一共需要递归n次,每次需要n时间,总体复杂度为O(n^2)。平均总体时间复杂度为O(nlogn)。

空间复杂度 O(logn):每次递归需要的空间是固定的,总体空间复杂度即为递归层数,因此平均/最好空间复杂度为O(logn),最坏空间复杂度为O(n)

堆排序

就是完全二叉树,通常用数组实现

数组如何映射到堆:i 位置(下标)

  • 左孩子:2*i+1
  • 右孩子:2*i+2
  • 父:(i-1)/2

堆结构:

  • 大根堆:每一颗子树,根是最大值
  • 小根堆:每一颗子树,根是最小值

两个最重要的操作

  • 如何构成:不断根父节点比较并交换,直到比根节点小
  • 大根堆pop最大值:把数组最后一个数放到根节点,并调整堆结构

维护堆结构的时间复杂度非常低:O(logn)

排序时间复杂度O(nlogn)

  1. 先构造堆
    1. 一个一个加进来
    1. 如果用户直接提供了一个完全二叉树,可以从叶子节点开始,依次进行每棵树的堆化
  2. 再从根不断取值 

空间复杂度:O(1)

小根堆/大根堆在java里面就是优先级队列:PriorityQueue(默认小根堆)

计数排序

不基于比较的排序:计数排序不是比较排序,排序的速度快于任何比较排序算法

数组下标表示值,数组值表示值等于‘下标’的数据的数量。

通过这个数组,可以很简单的还原排序后的原数组

时间复杂度:O(n)

缺点:受限于数据的特点

基数排序

基数排序是一种非比较型整数排序算法,也使用了桶概念其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。

几进制就可以准备几个桶

桶排序

  • 基数排序:根据键值的每位数字来分配桶;
  • 计数排序:每个桶只存储单一键值;
  • 桶排序:每个桶存储一定范围的数值;

排序稳定性 

排序完,值相同的数,相对位置是不变的,那么就是存在稳定性的。

目前没有找到复杂度O(nLogn)/O(1)/稳定的排序算法

综合排序

将几个排序结合起来,发挥各自的优势。

Arrays.sort():

如果是基础类型,那么就是使用快排;

如果不是基础类型,就使用归并排序(为了保证稳定性)

查找算法

顺序查找

O(n)

二分法

时间复杂度:O(logn)

哈希表

HashSet & HashMap底层结构是一样的,区别就是是否有伴随数据value

CRUD的时间复杂度是O(1)

放入哈希表的东西,如果不是基础类型就是引用传递,即存储对象的地址。

有序表

TreeSet & TreeMap:底层结构是一样的,区别就是是否有伴随数据value

与哈希表区别:有序表把key按照顺序组织起来

性能上差于哈希表:O(logn)

操作:

  • Hashset/map的操作
  • firstKey
  • lastKey
  • floorKey
  • ceilingKey

红黑树,AVL树,size-balance-tree等都是有序表结构,只是底层实现不同。

自定义类型需要提供比较器

单链表/双链表 

反转单/双向链表

快慢指针

判断两个链表相交的节点 

判断有环无环/求环的第一个节点也是利用快慢指针

Java LinkedList(链表) 类似于 ArrayList,是一种常用的数据容器。

与 ArrayList 相比,LinkedList 的增加和删除的操作效率更高,而查找和修改的操作效率较低。

以下情况使用 ArrayList :

  • 频繁访问列表中的某一个元素。
  • 只需要在列表末尾进行添加和删除元素操作。

以下情况使用 LinkedList :

  • 你需要通过循环迭代来访问列表中的某些元素。
  • 需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作。

LinkedList实现了Queue接口

二叉树  

用递归和非递归实现二叉树的前序中序后序的遍历

深度优先(前中后序就是深度优先)

广度(宽度优先)优先遍历:使用队列

求最大层宽度;(hash表法和指针计数法

判断搜索二叉树

每一颗子树; 左树节点《自己《右树节点

可通过中序遍历判断是否是搜索二叉树

可以通过树形动态规划分治分成左右子树通过递归来求解

判断完全二叉树

从左到右依次变满

按宽度遍历:

  • 有右孩子,没有左孩子,return false
  • 第一个叶子节点之后所有节点必须是叶子结点

判断满二叉树

判断层数与节点个数关系

可以通过树形动态规划分治分成左右子树通过递归来求解

判断平衡二叉树 

任何子树,左树和右树的高度差不超过1

可以通过树形动态规划分治分成左右子树通过递归来求解

二叉树的序列化/反序列化

例如:以中序遍历序列化,就用中序遍历反序列化

也可以用分治来做序列化

通过队列实现反序列化+分治 

并查集

并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。

并查集的思想是用一个数组表示了整片森林(parent),树的根节点唯一标识了一个集合,我们只要找到了某个元素的的树根,就能确定它在哪个集合里。

表示方式

  • 邻接表
    • A:B,C
    • B:A
    • C:A,D
    • D:C
  • 邻接矩阵
    • 可以用数值表示距离/权重
  • 对象结构:
    • 图=点集+边集

分类:有向图/无向图

构成:点,边

图的深度优先遍历dft

利用栈实现

图的广度优先遍历bft

利用队列实现

拓扑排序算法

有向无环图排序-例如任务执行顺序,包依赖解析顺序等问题

算法:优先处理入度为零的点

K(Kruskal)算法生成最小生成树

要求无向图

最小生成树:图里面保留尽可能少数量的边来保证连通性,并保证权值的和是最小的

按权值从小到大依次连接,如果加上某一条边会形成环,则跳过它。

  • 可以自己通过为点设定连通集合实现
  • 更简单是通过并查集来实现

P(prim)排序算法生成最小生成树

要求无向图

Dijkstra算法求最短路径

Dijkstra 算法是一个基于「贪心」、「广度优先搜索」、「动态规划」求一个图中一个点到其他所有点的最短路径的算法,时间复杂度 O(n2)

如何加速:通过自己实现堆来对源代码进行加速 

前缀树

https://zhuanlan.zhihu.com/p/28891541

通过字符串序列构造树 abc bcd abe afg -> tree

用途:存储字符串,非常方便查询

Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

思想

递推

一种计算机算法

递归

与递推相对应

动态规划

https://cloud.tencent.com/developer/article/1817113

思路:

  • 穷举分析
  • 确定边界
  • 找出规律,确定最优子结构
  • 写出状态转移方程

一道动态规划问题,其实就是一个递推问题。假设当前决策结果是f(n),则最优子结构就是要让 f(n-k) 最优,最优子结构性质就是能让转移到n的状态是最优的,并且与后面的决策没有关系,即让后面的决策安心地使用前面的局部最优解的一种性质

分治vs动态规划

  • 共同点:两者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小的子问题,然后将子问题的解合并,最终得到答案。
  • 不同点:分治法将分解后的子问题看成相互独立的,通常用递归来做。动态规划将分解后的子问题理解为相互间有联系,有重叠部分,需要记忆,通常用迭代来做。

递推vs动态规划

  • 递推 是一种计算机算法,通常用来将一个递推函数 转化成一个线性或多项式时间(取决于递推函数的参数个数)的求解程序。
  • 动态规划 是一个运筹学算法,通常可以用来将一个满足特定条件的决策最优化问题 转化成一个递推函数。

写动态规划的思路

  1. 写递归版本的代码来处理问题
  2. 记忆化搜索-》用缓存结构避免重复计算,记一下中间的一些计算结果,以便重复利用
  3. 通过多位表结构来存储中间的一些计算结果:二维数组+状态转移方程(可变参数的数量决定了是几维表通常是二维表避免不必要的变量)

如何使得动态规划能够优于暴力递归?

有重复计算的部分一定要将值存储下来时间复杂度会优化很多

分治法(Divide and Conquer)

将问题拆分成类似的小规模问题,通常采用递归方式处理

  • 归并排序
  • 快排
  • 汉诺塔问题
  • 逆序一个stack,使用递归不用额外数据结构 

回溯深度优先

回溯算法,又称为“试探法”。解决问题时,每进行一步,都是抱着试试看的态度,如果发现当前选择并不是最好的,或者这么走下去肯定达不到目标,立刻做回退操作重新选择。这种走不通就回退再走的方法就是回溯算法。

回溯与递归

回溯是可以通过递归实现的,当然也可以通过栈;

回溯最重要的一步是:还原数据

例子

打印一个字符串的所有子字符串

打印一个字符串的所有排列组合-》更进一步,如何去重?-递归过程中剪枝去掉对一些分支的探索

分支限界广度优先

分支限界法(branch and bound method)是求解纯整数规划或混合整数规划问题的经典方法,在上世纪六十年代由Land Doig和Dakin等人提出。这种方法灵活且便于用计算机求解,目前已经成功运用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。算法基本思想如下:

以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树

分支限界法中,每一个活结点只有一次机会成为扩展结点,活结点一旦成为扩展结点,就一次性产生其所有儿子结点,其中导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中

然后从活结点表中取下一结点成为当前扩展结点

重复上述结点扩展过程,直至到找到所需的解或活结点表为空时为止

贪心

贪婪算法(贪心算法)是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法

需要证明:局部最优-》全局最优 这个其实是难点;往往确认了某种局部最优的方法可以带来全局最优之后,代码实现是非常简单的,但是确定“某种局部最优的方法可以带来全局最优”这个理论是正确的,才是最复杂的点。这个是数学层面的东西更多了。

有的问题用贪心并不能获得全局最优解答,例如背包问题:

https://blog.csdn.net/qq_16234613/article/details/52235082

贪心算法经常会用到排序/大小根堆因为贪心往往是优先选择某一个极端值

例题:

哈夫曼编码问题

使用小根堆进行处理:

https://blog.csdn.net/xiangjunyes/article/details/106026830

最难的是证明算法(策略);代码实现并不复杂;

经典问题

N皇后问题

N*N的棋盘上,摆放N个皇后,任何两个不在同一行,列,斜线上。有多少种摆法。

暴力递归采用深度优先遍历的方法 –》   也是回溯算法

时间复杂度O(pow(n,n)) -》 能够优化常数时间:用位运算进行加速,优化十分明显 

此条目发表在Uncategorized分类目录。将固定链接加入收藏夹。

算法温习》有38条回应

  1. pupis说:

    Приложения для ставок на спорт доступны бесплатно — просто скачайте легальные БК и начните выигрывать

  2. starzbet说:

    Ищете рабочее зеркало? Перейдите на 888Starz рабочее зеркало

  3. gruzpoputno说:

    Если вы хотите отправить груз с минимальными затратами, попутная доставка — это оптимальный выбор

  4. nakrutkapf说:

    Чтобы сайт стал популярнее, пройдите курс накрутки ПФ и улучшите поведенческие факторы.

  5. Грузоперевозки Новосибирск Барнаул — это удобный вариант для экономичной доставки.

  6. onexslotsfun说:

    Для доступа к казино скачайте 1xslots бесплатно и начните выигрывать.

  7. Lucky Jet отзывы помогут выбрать оптимальную стратегию и понять, как работает игра.

  8. pupis说:

    Легальные букмекерские приложения помогают скачать БК на Android и наслаждаться игрой в любое время

  9. raketaigra说:

    Загрузите ракету на деньги скачать и начните игру, которая объединяет риск и азарт.

  10. Play and win with 888Starz Casino and get extra rewards with 888LEGAL.

  11. Con 1xslot app tendras acceso a los mejores juegos y promociones.

  12. brotapova说:

    They sell a good range of liquid SARMs priligy medication

  13. apkportalnik说:

    загрузить приложения онлайн казино https://www.alfarosa.com.pe/2024/11/kent-casino-2/

  14. Euro 2024说:

    Stay informed on international affairs, government news, and sports highlights.
    Our dedicated reporters deliver timely reporting 24/7.
    Euro 2024

  15. Stay informed on world events, political developments, and game results.
    Our expert team bring you real-time updates non-stop. World news in English

  16. Ищете выгодную ипотеку? Сравните десятки предложений от банков Казахстана, чтобы найти подходящие условия для покупки жилья вашей мечты.

    Микрокредиты Курсы валют .

  17. Кто ты есть на самом деле? В чем твое предназначение?
    В каком направлении лежит твой путь и как
    тебе по нему идти?
    Дизайн Человека расскажет об этом!

    – Снимает давление социальных стереотипов
    – Уменьшает внутренние конфликты – Даёт ощущение уникальности – Даёт конкретные рекомендации по принятию решений
    – Даёт право быть собой – Снимает давление
    социальных стереотипов – Даёт
    конкретные рекомендации по принятию решений
    – Даёт ощущение уникальности – Снимает
    давление социальных стереотипов

    Всего есть четыре типа (манифесторы, генераторы, проекторы, рефлекторы) людей на планете и у
    каждого из них есть стратегия принятия решения.

  18. Кто ты есть на самом деле?
    В чем твое предназначение?
    В каком направлении лежит
    твой путь и как тебе по нему идти?

    Дизайн Человека расскажет об этом!

    – Укрепляет доверие к себе – Снижает тревожность при выборе – Снимает чувство вины за “неправильность” – Позволяет выстроить эффективную
    стратегию жизни и карьеры – Даёт опору на природные механизмы – Приносит чувство согласия с собой –
    Даёт конкретные рекомендации по принятию решений
    – Уменьшает внутренние конфликты – Снижает тревожность при выборе

    Всего есть четыре типа (манифесторы,
    генераторы, проекторы, рефлекторы) людей на планете и у каждого из них есть стратегия принятия
    решения.

  19. Кто ты есть на самом деле?
    В чем твое предназначение? В каком
    направлении лежит твой путь и как тебе по нему идти?

    Дизайн Человека расскажет об этом!

    – Приносит чувство согласия с собой
    – Даёт конкретные рекомендации по
    принятию решений – Снимает
    давление социальных стереотипов
    – Позволяет жить в согласии со своей природой –
    Снижает тревожность при выборе
    – Помогает понять свои природные таланты и способности
    – Приносит чувство согласия с собой – Даёт право быть собой
    – Снимает чувство вины за “неправильность”

    Типы известны нам, как: Манифестор, Рефлектор,
    Генератор и Проектор.
    Определить тип личности. Узнать тип.
    4 типа людей. Дизайн Человека.

  20. Насладитесь игрой в казино онлайн, стремитесь к джекпоту.
    Проникнитесь атмосферой казино онлайн, играйте как профессионал.
    Находите лучшие игровые площадки, доверьтесь профессионалам.
    Увеличьте свой банкролл с казино онлайн, делая ставки на спортивные события.
    Присоединяйтесь к сообществу азартных игроков, получайте удовольствие от игры.
    Достижения ждут вас в казино онлайн, достигайте финансовой независимости.
    Почувствуйте реальный азарт игры в казино онлайн, становясь настоящим профи.
    Выберите свой идеальный вариант развлечения, играйте на любом устройстве.
    Преуспейте в азартных играх вместе с нами, зарабатывайте крупные суммы.
    Забудьте о скучных моментах, играя везде и всегда, погружаясь в мир азарта.
    Разнообразные игры помогут вам насладиться моментом, получая яркие эмоции.
    Продолжайте играть в казино онлайн и побеждать, получая щедрые бонусы.
    Наслаждайтесь свободой и возможностью выигрывать, получайте удовольствие от игры в любое время дня и ночи.
    Добейтесь успеха с нашей помощью, практикуя различные подходы.
    онлайн казино беларусь онлайн казино .

  21. Пройти техосмотр на Московском шоссе в Санкт-Петербурге стал проще, чем когда-либо . На Московском шоссе работает надежный центр техосмотра, где водители могут проверить свои автомобили . Опытные мастера гарантируют соблюдение всех требований .

    Для оформления техосмотра на Московское шоссе, Санкт-Петербург, потребуется минимальный набор документов . Водители оценят удобное расположение пункта . Высокая скорость обслуживания позволит вам получить техосмотр без задержек.

    Техосмотр на Московском шоссе соответствует всем стандартам . Центр оборудован всем необходимым для проверки , что позволяет получить точные результаты . Выбирайте удобный и надежный пункт на Московском шоссе.
    Лучший техосмотр Московское шоссе 13

  22. Официальный сайт ГГУ имени Ф.Скорины, с актуальными новостями о университете.
    Узнайте все о образовательной программе ГГУ имени Ф.Скорины, для вашего профессионального роста.
    Получите высшее образование в ГГУ имени Ф.Скорины, чтобы расширить свой кругозор и навыки.
    Углубитесь в науку с ГГУ имени Ф.Скорины, чтобы выделяться среди других специалистов.
    Познакомьтесь с факультетами и исследовательскими лабораториями ГГУ имени Ф.Скорины, и вы сможете раскрыть свой потенциал.
    Следите за новостями и событиями в ГГУ имени Ф.Скорины, чтобы быть в центре научной и академической жизни.
    Примите участие в проектах и программе стажировок в ГГУ имени Ф.Скорины, для практического применения теоретических знаний.
    Общайтесь с преподавателями и студентами ГГУ имени Ф.Скорины, и вы найдете сообщество, где вас поймут и поддержат.
    Станьте частью ведущего университета, для вашего личностного и профессионального развития.
    Воплотите свои учебные и научные амбиции в жизнь, для вашего образования и научной карьеры на высшем уровне.
    Завершите свой путь обучения в ГГУ имени Ф.Скорины с отличием, для вашего признания и успеха в образовательной и научной сфере.
    Откройте для себя мир знаний и исследований в ГГУ имени Ф.Скорины, для вашего успешного старта в научной и академической сфере.
    Участвуйте в кружках и клубах университета, для расширения круга общения и дружеских связей.
    Обучитесь на кафедрах и специализации в ГГУ имени Ф.Скорины, для вашего професс
    education https://gsu.by/ .

    One of the leading academic and scientific-research centers of the Belarus. There are 12 Faculties at the University, 2 scientific and research institutes. Higher education in 35 specialities of the 1st degree of education and 22 specialities.

  23. Для стабильного входа используйте 1xslots сайт зеркало.

  24. Casino games offer an exciting experience for those who enjoy high stakes. Whether you’re into classic slots, there’s something for everyone. Many casinos offer promotions to keep gamblers engaged.

    For online gamblers, flexibility of virtual platforms is exceptional. With secure transactions, online casinos provide a seamless gaming experience. You can explore your favorite games from the comfort of your home.
    https://unece.org/ru/info/events/event/19455

    Playing with limits is key for an enjoyable experience. Many platforms implement measures to set limits. Remember, enjoyment is what makes gambling worthwhile.

  25. евро в тенге юань в тенге .

    Конвертация валют еще никогда не была такой простой! Платформа предоставляет актуальные курсы тенге, рублей, долларов и других валют с быстрым расчетом.

  26. Nice answer back in return of this matter with solid arguments and
    explaining everything regarding that.

发表评论

您的电子邮箱地址不会被公开。