记录一下计算机与算法学习的细节

107426 · 发表于 2020-10-10 23:03:38

对数级O(lgn)速度其实很快，接近常数级O(n)。 lg100000000=30(近似，另外计算机中lg以2为底)。所以O(nlgn)比O(n^2)性能的提升比想象中大得多。

程序加载后，OS给其分配的内存分为堆区和栈区，以前一直不知道堆区和数据结构中的堆有什么联系。后来听老师说，堆区主要用来malloc申请内存，因为每次都要找到合适的大小，所以导致堆区的内存碎片较多，像马蜂窝一样。
因为每次都要找到最大的内存块，所以大顶堆这种数据结构特别适合管理堆区的内存，建堆可以控制在lg级，而最大的内存块几乎可以随时取出来。所以堆排序算法并不常用，实际中用的更多的是堆这种数据结构本身。

O(n^2)排序算法慢的原因是因为最坏时要把每两个元素都进行比大小，比的次数自然是平方级。所以要想研究出更快的排序算法，就要从减少元素的比较次数入手。比如快速排序算法，选好pivot值进行一趟排序后，比他小的部分就不用再和比他大的部分进行比较了，这样便减少了比较次数。

107426 · 发表于 2020-10-12 04:08:05

怎样继续盖楼啊

107426 · 发表于 2020-10-12 04:08:30

20201012
一般来说，一个进程的内存限制是2G，而每个线程要预留1M的内存空间，所以理论上一个进程可以开最多2048个线程（当然实际肯定要比这少）。可以通过修改默认线程空间的大小达到突破2048限制的目的，不过没什么实用价值，因为线程多了CPU的调度开销也会随之变大。

107426 · 发表于 2020-10-14 02:11:51

20201014
基于比较排序的算法的性能是有上限的，大部分人都知道是nlgn，但是为什么多年的研究都突破不了nlgn呢，其实数学早已给出了答案。
每一种基于比较的排序算法，都可以看作一棵二叉排序树，叶子节点代表每一种排序结果，算法的不同就体现在构造这棵树的不同方法。叶子到树根的距离表示比较次数，也就是时间。由二叉树的性质，2^h>=k，k为叶子节点，且所有的排序结果有n!个，所以h>=lg(n!)，即T(n)>=lg(n!)，由斯特林公式，可以得到，T(n)>=O(nlgn)，或者近似地看，lg(n!)=lgn+lg(n-1)+…+lg1，复杂度就是nlgn，这便是问题所在。
但是不论是什么排序算法，都不可能小于O(n)，因为你至少每个元素看一眼都是线性时间。又因为上次说到，lgn接近常数级，所以nlgn的排序算法已经很优秀了。

107426 · 发表于 2020-10-14 02:19:30

同为nlgn，为什么快排的性能要优于归并排序呢，这是因为除了比较，还有一个开销便是搬动元素，归并排序需要大量读入写出，而快排只需要把比pivot大的向后挪就行了。但是归并排序很适合外部排序，因为一次将两个队首元素读入就OK了。

107426 · 发表于 2020-10-28 13:01:54

#关于c语言中主函数的参数#
c语言主函数有两个参数，一个是argc，一个是argv。这两个参数都是在运行时传入的命令行参数，Windows由于很少用命令行编译执行，所以不常见到。第一个参数代表传入参数的个数，argument count。第二个代表是指向内存的二级字符指针argument vector，并且argv[0]一定是程序名称，并包含了完整路径。所以实际参数个数是argc-1个。

41976 · 发表于 2020-10-29 08:43:05

高端啊，学习了

107426 · 发表于 2020-11-10 15:21:00

20201110#多源点最短路径算法：弗洛伊德算法与动态规划的关系#
在数据结构的学习中，关于图的算法有诸如迪杰斯特拉算法，Bellman-Ford算法等，然而之前只是为了应付考试或者简单学习算法流程，所以总是学一遍，忘一遍，不深刻理解它是怎么来的，就总也记不住，反正我是这样。所以，今天重新学习了一下多源点最短路径算法：弗洛伊德算法，并从动态规划的角度重新理解它。
简单回顾一下动态规划思想，动态规划常用于子问题重叠的情况，当不同的子问题有公共的子子问题时（子问题的求解递归进行），无脑递归它会反复求解那些重复的子问题，造成计算资源的浪费。而动态规划就是将子子问题只求解一次，从而无需重复计算。它的一个最基本特征是该问题会用到子问题的最优解，子问题的又会用到子子问题的最优解。

看一个简单的例子：先描述一下我们要解决的问题，求出该图中所有节点之间的最短距离。当然我们的目的是寻找让计算机解决这个问题的通用的办法，我们用眼睛看当然很容易，但当图规模特别大时，就得靠计算机了。

为了便于表示，我们可以用二维矩阵来表示各个节点之间的距离。

这是初始情况，在不经过任何节点的情况下，各个节点之间的距离。之后所有的操作都在这个矩阵上进行。

再来说说如何用动态规划来解决这个问题：假如要求两节点Vi和Vj之间的最短距离，假设还有k个其它节点。这个问题的子问题是：除去第k个节点，i和j之间经过k和不经过k两个子问题。此时假设已求得包含了前k-1个中间节点的最短路径。经过k的最短距离就是Dik+Dkj;不经过k的最短距离就是Dij，这里的D都是在利用了k-1个中间节点后的求得的最短距离。所以只要在这两个子问题中挑出最小值即可。这时子子问题产生了，利用k-1个中间节点的i和j之间，i和k之间，k和j之间的距离怎么求呢。这时就可以推给图包含前k-2个中间节点的最短距离，有点像数列中的递推公式。这时问题的最优解就利用了子问题的最优解，这便是动态规划问题都要满足的最优子结构。

如下便是多源点最短路径的递推式：

我们的思路是自顶向下递推，而我们求解问题的思路便是自底向上求解，因为自底向上的话我们可以将子问题的最优解记录下来，求解上层问题的时候直接查就行了。
再回到开始的实例，我们以节点1，2，3的顺序开始包含：
初始包含0个节点：

包含节点1：

这里举个例子3到2的距离是如何从无穷大更新到7的：此时k=1，也就是在包含k-1=0个节点的基础上（初始矩阵）计算，
d(3,2)=无穷大；d(3,1)+d(1,2)=3+4=7;选择较小的7更新矩阵。（注意这里的3+4不是从图上看的，而是在C0那个矩阵里找的，因为计算机可不会看图，而且矩阵的9个值都要挨个算一遍，只不过有的不需要更新）。
然后包含节点2：

这里看一下1到3的最短距离是怎么更新到6的：此时k=2，也就是在包含k-1=1个节点的基础（即矩阵C1）上计算，d(1,3)=11;d(1,2)+d(2,3)=4+2=6;选择更小的6更新矩阵。同样这里的值都是从C1矩阵中找的，这里C1就是C2的子问题。求解C2利用的子问题的最优解。
然后包含节点3：

此时这个矩阵中便包含了任意节点之间的最短距离，在问题规模特别大时，计算机可以利用这个方法很快求得全局的最优解。这便是多源点最短路径的佛洛依德算法，下面给出该算法的伪代码。

C={dij} // 初始化矩阵
for k = 1 to n
for i = 1 to n
for j = 1 to n
dij = min(dij, dik + dkj)
return C

该算法的时间复杂度是O(n^3)，该算法不仅代码简洁，而且是一个很巧妙很棒的算法，可以帮助我们快速算得图上任意两个节点的最短距离，在通信路由领域用途广泛。

107426 · 发表于 2020-11-24 17:21:04

希尔伯特第十个问题>>费马大定理证明>>计算机学科产生

[私人活动] 记录一下计算机与算法学习的细节