Questions tagged [algorithm]

我正在尝试对算法复杂性进行一些猜测，但是每次我尝试使用指数时间进行猜测时，我的猜测/验证方法似乎都失败了。我确定我做错了什么荒谬的事情，我自己找不到。

例如，如果我有递归T(n) = 2T(n-1) + T(n-2) + 1，其中 T(1) = 0 和 T(2) = 1。

通过迭代几次并插入值 n=3,4,5,6,7,8... 我们可以观察到对于 n>=8 的任何值，T(n) > 2^n，因此 2 ^n 不是上限。

因此，知道这些信息后，我尝试猜测 T(n)=O(2^n)

T(n) <= C(2^n)

2T(n-1)+T(n-2)+1 <= C(2^n)

2C(2^(n-1))+C(2^(n-2))+1 <= c(2^n)

C(2^n)-C(2^n+2^(n-2)) >= 1

C(-2^(n-2)) >= 1

C >= 1/(2^(n-2)) | 当 n-> 无穷大时，表达式变为零

这不是说我的猜测太高了吗？但是，我知道事实并非如此。谁能看到我到底在哪里扼杀这个理论？谢谢。

我确实必须处理非常大的纯文本文件（超过 10 GB，是的，我知道这取决于我们应该称之为大的），而且行很长。

我最近的任务涉及基于另一个文件中的数据进行一些行编辑。

数据文件（应该修改）包含 1500000 行，每行例如 800 个字符长。每一行都是唯一的，并且只包含一个身份号码，每个身份号码都是唯一的）

修改文件是例如1800 行长，包含一个身份号码，以及一个应该在数据文件中修改的数量和日期。

我刚刚将修饰符文件（使用 Vim 正则表达式）转换为 sed，但效率非常低。

假设我在数据文件中有这样一行：

我需要修改 300 字符部分中的数据。

基于修饰符文件，我想出了这样的 sed 行：

所以我有1800行这样的。

但我知道，即使在非常快的服务器上，如果我执行

它非常慢，因为它必须读取每个模式 x 每一行。

没有更好的方法吗？

注意：我不是程序员，从未（在学校）学习过算法。我可以在服务器上使用 awk、sed、perl 的过时版本。

我正在编写一个 HTML 刮板程序，当它从页面中抓取 HTML 时，它会返回 HTML，我想抓取所有大写字母的单词，然后将这些单词存储到数据库中。我现在的问题是我无法正确的算法来解析我返回的 HTML 的每一行以存储单词。这基本上就是我正在使用的格式。重要你会注意到大写字母的单词总是第一个，所以基本上我只需要查看每行 HTML 的第一个字母，然后确定整个单词是否大写。如果是，那么我想将这个词添加到列表中，如果不是，那么我想转到下一行......所以它看起来像这样......

姓名列表 ----> 应跳过此行，因为第一个单词并非全部大写
AARON ....
ABRAHAM ....
ANGELA ...
AMY ...
ASHLEY ....

我能够获得上述格式的 html，但现在我很难编写算法来获取每行的第一个单词，然后

有没有人知道如何在不使用外部解析而只使用循环和列表的情况下做到这一点。谢谢，感谢您的帮助

我有以下问题：

1. 有一个由 6 个数字组成的数组，每个数字最多两位数。
2. Y是一个数组，其第i个元素是第一个数组的前i +1个元素的总和。
3. 通过键盘接受数字输入。如果它与Y中的一个数字匹配，则显示一条消息；如果没有，请重新启动程序。

这是我正在考虑的算法：

• 初始化空数组 [x] & [y]
• 6.times.map{ Random.rand(1..99) }
• 使用每个添加数字吗？
• 存储在数组 [y]
• 将输入与 == 数组 [y] 进行比较
• 如果任何实例匹配显示消息，否则重新启动

对于这个问题的任何指导或帮助，我将不胜感激。

我有一张我声明如下的地图：

我将值插入到地图中：

然而，

cout<<index[y]; // for any number y not in指数gives me 0

1. 当我在检查地图中不存在的键时获得值0时，如何可靠地找出地图中是否存在键？
2. 我正在使用地图来尝试找出两个集合是否不相交，同样我正在使用地图和两个向量来存储输入。这有什么破旧的吗？我应该使用其他一些数据结构？

当 XML 采用以下形式时，我在解析 XML 时遇到问题：

我已经想出了如何解析这样的第一级孩子：

使用这种代码：

如何解析作为“汽车”子标签的多个“汽车”标签？

我又接到了学校的任务。这一次，我的老师给我的任务是创建算法来计算图片上有多少只鸭子。

图片与此类似：

我想我应该使用模式识别来搜索上面有多少只鸭子。但我不知道每只鸭子都匹配哪种模式。

我写了一个格雷厄姆扫描凸包算法的实现，对于测试数据，我使用了这些点

根据我的程序，凸包是

但是，我希望凸包是

我也用https://github.com/shadwstalkr/GrahamScanDemo/尝试了我的一组点，这也给出了相同的解决方案。经过多次抱怨和抱怨后，我在维基百科上读到“如果对象内的每一对点，连接它们的直线段上的每个点也在对象内，则该对象是凸的。”

在画出我的观点和船体之后。看来我的程序在该定义内生成了一个对象，但这是否意味着仅按角度排序就会给出一个凸包，而在包中没有任何点？

我是否不了解凸包实际上是什么并且我正在解决一个不同的问题，或者我的实现和 shadwstalkr 都不正确？

所以，我正在阅读这篇维基百科文章中的剪辑。它似乎对所有游戏都非常重要，所以，我必须这样做，还是由 Three.js 甚至 WebGL 自动完成？谢谢！

假设您从“流”源读取数据项和相关分数（即不可能进行随机访问或多次传递）。

什么是在任何时候只保留内存中迄今为止遇到的权重最低的那些元素的最佳方法。我会对“Java”的做法感兴趣，成语越短越好，而不是算法（“使用搜索树，插入新元素，如果超出大小则删除最大的元素”）。

下面是我想出的解决方案，但是我觉得有点冗长，而且有些行为可能是出乎意料的（不同分数的同一个项目可能会保留多次，而相同分数的相同项目只保留一次） . 我也觉得应该为此存在一些东西。

有一个类似的问题，但它不包括流源/内存要求： Find top N elements in an Array