算法认知

① 关于算法

阿朱对于算法的了解不多，总结如下，希望多多交流，改正瑕疵。

算法推荐主要有5种方式：

基于内容推荐：这是基于用户个人兴趣的推荐。根据用户个体的历史行为，计算对内容特征的偏好程度，进而推荐出与用户特征偏好匹配的内容。

协同过滤算法：这是基于群体的推荐。基于用户的相似度、内容的共现度，以及基于人口特征将用户聚集为不同群体来推荐。（解释一下：常见的协同过滤算法有两种，一种是基于用户的（user-based），也即计算用户之间的相似性，如果A和B的兴趣相近，那么A喜欢的电影，B也很有可能喜欢。另一种是基于物品的（item-based），也即计算物品之间的相似性，如果电影C和电影D很相似，那么喜欢电影C的人，可能也会喜欢电影D。）

扩展推荐：基于用户兴趣点、内容类别等扩展。（你喜欢历史资讯，我推考古、寻宝的资讯给你）

新热推荐：基于全局内容的时效性、热度推荐。（在产品初期同时缺乏用户数据和内容数据时，内容分发效率很低。使用基于内容推荐算法效果不显着，而使用一些热点话题可在保证一定流量的同时，不断通过用户的个人行为（点赞、评论、浏览、收藏）来逐步精确用户画像和进行内容沉淀，为之后的个性化推荐做准备）。

环境特征：基于地域、时间、场景等推荐。（知乎上你们市的牙科诊所广告、婚庆广告）

每种算法的效果不一，组合味道更佳，因此很多公司都是采用“算法矩阵”的方式来推荐feed。（后文也会谈到这一点）

优势:

内容质量审核、社区治理（辱骂、撕逼），推荐商品，减少人工运营成本。

源源不断推荐给你感兴趣的feed，提升了用户粘性，商业化的潜力进一步加大。

让用户 kill time 的需求更好地被满足，增强用户体验

弊端：

1.算法本身或者算法背后的人产生技术错误——只要是人写的算法，就一定有出错的概率，比如德国居民凌晨发飙的智能音箱、失控的Uber自动驾驶汽车就是程序上的Bug导致的，这一类我们克服的办法其实相对简单。但对于另一种人为算计消费者的算法有时候可能我们就无能为力了，比如大数据杀熟现象，无论真实与否，这类问题往往很难识别，因此也加大了监管的难度；（抖音视频里你见不到“钱”字，只能看到“Q”来代替）

2.算法对于人性部分的忽略——现在的人工智能离真正理解人类的感情和行为依然有巨大的鸿沟，Facebook提醒你给去世的亲人发生日祝福背后本质的原因在于AI无法真正理解死亡对于人类意味着什么；因此需要人机结合（平台人工参与，用户举报等自治措施），不能单独依靠算法。

3.算法训练数据本身的偏见——目前人工智能的基本逻辑是先构建一个合适的机器学习模型，然后用大量的数据去训练模型，然后用训练好的模型再来预测新的数据，这里边有一个非常重要前提就是输入数据的重要性，比如变坏的微软机器人Tay之所以产生问题就是因为输入的数据中本身就存在偏见，如果现实世界数据本身就存在偏见，那么预测结果也一定会有偏见；

先下结论吧：算法不会导致“信息茧房”

“社交媒体和算法推荐导致信息茧房”这一判断成立的一个重要前提是：我们只会点击那些我们熟悉的、赞同的内容，不断让机器加深对我们的印象：原来他们只喜欢看这些！

但在现实中，这个前提是过于简化的，乃至是错误的。

在个体层面，我们有着多样的阅读动机，受到各种认知偏见的影响，可能倾向于点击某些特定类型的内容，但绝不仅仅局限于自己认同的那些。

在社交层面：我们在大多数APP上都存在着社交关系，以及主动选择关注的帐号，这些都对我们能接触到的内容产生重要影响。一个在APP上拥有一定社交关系的人，不太可能陷入狭窄的视野当中。

在技术层面：在算法的分类里说了，每种算法都有其利弊，因此很多公司都是采用“算法矩阵”的方式来推荐feed。但在普罗大众眼里，算法=基于内容的推荐算法，而忽略了“基于内容的推荐算法”只是算法种类里的一种，其他类型算法也会被产品使用。

在企业层面：没有一个商场的经理，希望顾客每一次来到商场都只关注同一类别的商品。用户兴趣窄化对于商业化目标并不是一个好的选择。

博弈：

推荐太强了，关注力量就会弱。抖音沉浸式交互和基于内容的算法推荐是 kill time 的利器，推荐feed刷的过瘾了，你还会去刷关注feed吗？

共生：

算法有弊端，关注可以弥补或有所增益。推荐feed是忽略了人"社交性“这个特点，以知乎为例，关注的内容生产者传递给我们价值，所以我们需要一个途径来知道那几十个或上百的关注对象的产出内容。朋友圈满足我们窥探的信息需求，也同理。（另外从结果反推过程，大家看一下手里的B站、知乎、抖音、快手就清楚了）

② 什么是算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。
形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。

③ 一文带你认识30个重要的数据结构和算法

数组是最简单也是最常见的数据结构。它们的特点是可以通过索引（位置）轻松访问元素。

它们是做什么用的？

想象一下有一排剧院椅。每把椅子都分配了一个位置（从左到右），因此每个观众都会从他将要坐的椅子上分配一个号码。这是一个数组。将问题扩展到整个剧院（椅子的行和列），您将拥有一个二维数组（矩阵）。

特性

链表是线性数据结构，就像数组一样。链表和数组的主要区别在于链表的元素不存储在连续的内存位置。它由节点组成——实体存储当前元素的值和下一个元素的地址引用。这样，元素通过指针链接。

它们是做什么用的？

链表的一个相关应用是浏览器的上一页和下一页的实现。双链表是存储用户搜索键哗显示的页面的完美数据结构。

特性

堆栈是一种抽象数据类型，它形式化了受限访问集合的概念。该限制遵循 LIFO（后进先出）规则。因此，添加到堆栈中的最后一个元素是您从中删除的第一个元素。

堆栈可以使用数组或链表来实现。

它们是做什么用的？

现实生活中最常见的例子是在食堂中将盘子叠放在宽枝一起。位于顶部的板首先被移除。放置在最底部的盘子是在堆栈中保留时间最长的盘子。

堆栈最有用的一种情况是您需要获取给定元素的相反顺序。只需将它们全部推入堆栈，然后弹出它们。

另一个有趣的应用是有效括号问题。给定一串括号，您可以使用堆栈检查它们是否匹配。

特性

队列是受限访问集合中的另一种数据类型，就像前面讨论的堆栈一样。主要区别在于队列是按照FIFO（先进先出）模型组织的：队列中第一个插入的元素是第一个被移除的元素。队列可以使用固定长度的数组、循环数组或链表来实现。

它们是做什么用的？

这种抽象数据类型 (ADT) 的最佳用途当然是模拟现实生活中的队列。例如，在呼叫中心应用程序中，队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。

一种特殊且非常重要的队列类型是优先级队列。元素根据与它们关联的“优先级”被引入队列：具有最高优先级的元素首先被引入队列。这个 ADT 在许多图算法（Dijkstra 算法、BFS、Prim 算法、霍夫曼编码 ）中是必不可少的。它是使用堆实现的。

另一种特殊类型的队列是deque 队列（双关语它的发音是“deck”）。可以从队列的两端插入/删除元素。

特性

Maps （dictionaries）是包含键集合和值集合的抽象数据类型。每个键都有一个与之关联的值。

哈希表是一种特殊类型的映射。它使用散列函数生成一个散列码，放入一个桶或槽数组：键被散列，结果散列指示值的存储位置。

最常见的散列函数（在众多散列函数中）是模常数函数。例如，如果常量是 6，则键 x 的值是x%6。

理想情况下，散列函数会将每个键分配给一个唯一的桶，但他们的大多数设计都采用了不完善的函数，这可能会导致具有相同生成值的键之间发生冲突。这种碰撞总是以某种方式适应的。

它们是做什么用的？

Maps 最着名的应用是语言词典。语言中的每个词都为其指定了定义。它是使用有序映射实现的（其键按字母顺序排列）。

通讯录也是一张Map。每个名字都有一个分配给它的电话号码。

另一个有用的应用是值的标准化。假设我们要为一天中的每一分钟（24 小时 = 1440 分钟）分配一个从 0 到 1439 的索引。哈希函数将为h(x) = x.小时*60+x.分钟。

特性

术语：

因为maps 是使用自平衡红黑树实现的（文章后面会解释），所以所有操作都在 O(log n) 内完成；所有哈希表操作都是常量。

图是表示一对两个集合的非线性数据结构：G={V, E}，其中 V 是顶点（节点）的集合，而 E 是边（箭头）的集合。节点是由边互连的值 - 描述两个节点之间的依赖关系（有时与成本/距离相关联）的线。

图有两种主要类型：有稿巧行向图和无向图。在无向图中，边(x, y)在两个方向上都可用：(x, y)和(y, x)。在有向图中，边(x, y)称为箭头，方向由其名称中顶点的顺序给出：箭头(x, y)与箭头(y, x) 不同。

它们是做什么用的？

特性

图论是一个广阔的领域，但我们将重点介绍一些最知名的概念：

一棵树是一个无向图，在连通性方面最小（如果我们消除一条边，图将不再连接）和在无环方面最大（如果我们添加一条边，图将不再是无环的）。所以任何无环连通无向图都是一棵树，但为了简单起见，我们将有根树称为树。

根是一个固定节点，它确定树中边的方向，所以这就是一切“开始”的地方。叶子是树的终端节点——这就是一切“结束”的地方。

一个顶点的孩子是它下面的事件顶点。一个顶点可以有多个子节点。一个顶点的父节点是它上面的事件顶点——它是唯一的。

它们是做什么用的？

我们在任何需要描绘层次结构的时候都使用树。我们自己的家谱树就是一个完美的例子。你最古老的祖先是树的根。最年轻的一代代表叶子的集合。

树也可以代表你工作的公司中的上下级关系。这样您就可以找出谁是您的上级以及您应该管理谁。

特性

二叉树是一种特殊类型的树：每个顶点最多可以有两个子节点。在严格二叉树中，除了叶子之外，每个节点都有两个孩子。具有 n 层的完整二叉树具有所有2ⁿ-1 个可能的节点。

二叉搜索树是一棵二叉树，其中节点的值属于一个完全有序的集合——任何任意选择的节点的值都大于左子树中的所有值，而小于右子树中的所有值。

它们是做什么用的？

BT 的一项重要应用是逻辑表达式的表示和评估。每个表达式都可以分解为变量/常量和运算符。这种表达式书写方法称为逆波兰表示法 (RPN)。这样，它们就可以形成一个二叉树，其中内部节点是运算符，叶子是变量/常量——它被称为抽象语法树（AST）。

BST 经常使用，因为它们可以快速搜索键属性。AVL 树、红黑树、有序集和映射是使用 BST 实现的。

特性

BST 有三种类型的 DFS 遍历：

所有这些类型的树都是自平衡二叉搜索树。不同之处在于它们以对数时间平衡高度的方式。

AVL 树在每次插入/删除后都是自平衡的，因为节点的左子树和右子树的高度之间的模块差异最大为 1。 AVL 以其发明者的名字命名：Adelson-Velsky 和 Landis。

在红黑树中，每个节点存储一个额外的代表颜色的位，用于确保每次插入/删除操作后的平衡。

在 Splay 树中，最近访问的节点可以快速再次访问，因此任何操作的摊销时间复杂度仍然是 O(log n)。

它们是做什么用的？

AVL 似乎是数据库理论中最好的数据结构。

RBT（红黑树） 用于组织可比较的数据片段，例如文本片段或数字。在 Java 8 版本中，HashMap 是使用 RBT 实现的。计算几何和函数式编程中的数据结构也是用 RBT 构建的。

在 Windows NT 中（在虚拟内存、网络和文件系统代码中），Splay 树用于缓存、内存分配器、垃圾收集器、数据压缩、绳索（替换用于长文本字符串的字符串）。

特性

最小堆是一棵二叉树，其中每个节点的值都大于或等于其父节点的值：val[par[x]]

④ 01 - 数据结构和算法的认识

了解数据结构和算法的一些基本概念，主要掌握时间复杂度的计算

数据结构是指所有数据元素以及数据元素之间的关系，可以看做是相互之间存在着某种特定关系的数据元素的集合，即可以把数据结构看成是 带结构的数据元素的集合 。

数据的逻辑结构是从逻辑关系上描述数据的，常常将数据的逻辑结构简称为数据结构。

集合：

树形结构：

图形结构：

逻辑结构在计算机中的存储方式。依赖于计算机语言

顺序存储结构：

链式存储结构：

索引存储结构：

散列（哈希）存储结构：

数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称，数据类型是数据结构在计算机的具体体现。

注意：

算法是对特定问题求解步骤的一种描述

特性： 有穷性、确定性、可行性、有输入、有输出

算法设计好后，还需要分析算法的优劣，从两方面考虑

一个算法由控制结构和原操作构成，算法的运算时间取决于两者的综合效果，算法执行时间大致为基本运算时所需时间与运行次数的乘积。因此一个算法的执行效率可以由其最基本的运算的执行次数来衡量。

计算公式： T(n)=O(f(n))

说明：

注意： O 的作用在于只求出T(n)的最高阶项，忽略低阶项和常数

O(1)
没有进行循环的算法中，基本运算次数与问题规模无关，所以是常数

对数阶 O(log2n)
次数为x，而2的x次方等于n，那么就是对数阶

线性阶 O(n)
只有一层循环

平方阶 O(n^2)

立方阶 O(n^3)
三层循环，肯定就是n^3了

排序：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) <O(2^n) < O(n!) < O(n^n)

也叫加权平均时间复杂度，将执行的概率也加入计算。

是一种特殊的加权平均时间复杂度，把耗时多的操作分摊到耗时低的操作。

这个时间复杂度 其实是O(1),而不是O(n)

算法空间复杂度是指计算算法所需的存储空间， 其计算公式为S(n) = n(f(n))
所以在考察算法的空间复杂度，主要考虑算法执行所需要的临时占用的存储空间大小的量度。

数组逆序,将一维v1.43数组a中的n个数逆序存放在原数组中.

复杂度计算:

说明：