问题标签 [computer-science-theory]

为什么 Floyd-Warshall 算法中有存储？如果使用链表而不是 N × N 矩阵，会不会比这更少？

I wish that John McCarthy was still alive, but...

From LISP 1.5 Programmer's Manual :

LISP can interpret and execute programs written in the form of S- expressions. Thus, like machine language, and unlike most other higher level languages, it can be used to generate programs for further execution.

I need more clarification about how machine language can used to generate programs and how Lisp can do it?

我注意到计算机科学中的每个基本数据结构本质上似乎都是递归的。例如图形、列表、数组、集合等。

这是为什么？有什么根本原因吗？是因为通过归纳更容易证明递归数据结构的属性吗？

有人将如何通过归纳来证明高度为 n 的二叉树有 2^(n+1)-1 个节点？

我刚刚阅读了Turing 的Computing Machinery and Intelligence，他提到了超感官知觉（#9）作为一个有效的论点：

“不幸的是，至少对于心灵感应而言，统计证据是压倒性的。”

我找不到任何这些统计证据，有人也知道他指的是什么吗？这是他生活的时代的产物吗？他的语气暗示他也不想相信。

我不确定这是否是最好的提问地点，但似乎有些相关。

我正在解决一个问题，我只是想确保我的工作是正确的，所以如果有人可以批评我，我将不胜感激。

问题：

有两个正在考虑的架构改进（A1 和 A2）。您已收到一张表格，其中显示了 5 个基准（B1-B5）中每个基准相对于基本系统的加速；这些加速是参考计算机的规格比率。

A1：B1 = 1.5，B2 = 4，B3 = 3，B4 = 2，B5 = 5

A2：B1=3，B2=1.5，B3=4，B4=4，B5=3

鉴于上述信息，应该选择哪种改进？

我的回答如下：

使用基线作为参考，改进的规格比 (A1/A2) 的几何平均值可用于确定哪个更好。

规格比例如下：

S1 = 1.5/3

S2 = 4/1.5

S3 = 3/4

S4 = 2/4

S5 = 5/3

几何平均值如下：(S1*S2*S3*S4*S5)^(1/5)，大致相当于 0.96。

因此，A1 大约只有 A2 的 96%，因此应该选择 A2。

再一次，我只是想看看我的想法是否正确。任何帮助表示赞赏。

EDIT1：使用 Mackie 的方法

以基准速度为基准，A0 如下：

B1=B2=B3=B4=B5=1

因此，Base 与 A1 (A0/A1) 的规格比的几何平均值将为：

((1/1.5) * (1/4) * (1/3) * (1/2) * (1/5)) ^ (1/5) = 0.35

Base 与 A2 (A0/A2) 的规格比的几何平均值将为：

((1/3) * (1/1.5) * (1/4) * (1/4) * (1/3)) ^ (1/5) = 0.34

然而，在这里比较 (Base/A1) 和 (Base/A2)，你会得到 0.35/0.34 = 1.03，这意味着 A1 比 A2 慢大约 3%？我的数学是在这里还是我为 A0 选择了错误的基准？我最初的方法似乎更简单，最初的问题是什么......

我有一个问题要编码。我有一个生成数字 0 到 n-1 的过程，我想在它生成第一个重复元素时停止它。*我正在寻找一种可以快速完成的数据结构。特别是，添加一个新元素并测试一个元素是否在结构中需要很快。预期的插入数量在 sqrt(n) 左右（生日问题），或者实际上更差一些（比如 sqrt(2n)），因为该过程略微偏向于唯一值。换句话说，它相当稀疏——处理多达 10 亿个数字时，只会使用大约 30 或 50,000 个值。

哈希集或某种自平衡二叉树似乎是正确的方法，但也许有更好的方法？对于小的 n，我认为位数组会更好，但我正在查看 10^9 左右的 n，这对于我认为实用而言太大了。

* 实际上，它不需要立即停止——如果它更有效，您可以在块中生成元素并不时检查。

注意：这最初是在 math.se 上发布的，但他们建议我在这里重新发布。它不是研究级别的，因此不适合 cstheory.se。

我正在尝试确定它是否是：O(1)。我该如何证明呢？在复杂度方面，log_b(n) 是 log(n)。O(log_2(n)-log_3(n))=O(0)=O(1) 也是这样吗？这似乎不是一个强有力的证据。此外，这不会渐近收敛，那么它怎么可能是 O(1)？

这是一个流行的问题：对 100 万个 32 位整数进行排序的最有效（时间复杂度）方法是什么。大多数答案似乎都同意，最好的方法之一是使用基数排序，因为假设这些数字中的位数是恒定的。当 CS 学生第一次学习基于非比较的排序时，这也是一个非常常见的思维练习。但是，我没有看到详细（或至少清楚地）描述的是如何为算法优化选择基数（或桶数）。

在这个观察到的答案中，基数/桶数的选择是凭经验完成的，对于 32 位 100 万整数，结果是 2^8。我想知道是否有更好的方法来选择该号码？在“算法简介”（第 198-199 页）中，它解释了 Radix 的运行时间应该是 Big Theta(d(n+k))（d=digits/passes，n=number of items，k=possible values）。然后它进一步说，给定 n 个 b 位数字，并且任何正整数 r <= b，基数排序在 Big Theta((b/r)(n+2^r)) 时间内对数字进行排序。然后它说：“如果 b>= floor(lg(n))，则选择 r ~= floor(lg(n)) 给出了在常数因子内的最佳时间......”。

但是，如果我们选择 r=lg(1million)~=20 != 8 正如观察到的答案所示。

这告诉我，我很可能误解了书中建议的“选择 r”方法，并且遗漏了一些东西（很可能），或者观察到的答案没有选择最佳值。

谁能帮我解决这个问题？先感谢您。

我是计算机科学研究的新手。我正在做一个研究项目，我的问题是如何检测 IEEE 出版物的影响因子？IEEE 是否提供此信息？