我当时正在从阅读的虚拟内存，发现了一条声明，它说：“如果我们让Sr S**，与引用字符串相反，那么在** S 上的OPT算法(最优页面替换)的页面错误率与 Sr**.上OPT算法的页面错误率相同。类似地，** S 上的LRU算法(最近使用最少)的页故障率与 Sr**.**
浏览 5提问于2014-07-16得票数 4
我需要证明最优的页面替换算法确实是最优的，但我不确定如何开始。我想也许可以通过矛盾来证明，但一旦我制定了一个替代声明，我不确定如何证明它的页面错误与OPT相等或更少。
浏览 8提问于2017-12-05得票数 0
我读到不变竞争是预期时间/最优时间的比率。但是，有一个固定的竞争意味着什么呢？
浏览 4提问于2009-05-30得票数 10
回答已采纳
1回答
“由指数置换p (i ) =(i+ k) mod n定义的n个元素的置换p称为k-旋转。”-- 我已经看过哈克的欢乐和第4A卷的Knu
浏览 1提问于2019-03-28得票数 1
1回答
回溯算法的每个递归步骤中的运算顺序对该特定算法的效率有多重要？在骑士之旅的问题上。
骑士被放置在一块空棋盘的第一块，按照国际象棋的规则，必须访问每个广场一次。操作顺序和测试算法。那么，我如何确定这些算法在特定运动顺序上的性能，或者更确切地说，如何才能达到一个(或一组)操作顺序，从而使该算法在执行时间上更有效。
浏览 8提问于2015-03-21得票数 2
1回答
.^2min_objective!(opt, myfunc)println("got $minf at $minx (returned $ret)")
浏览 4提问于2016-06-09得票数 3
回答已采纳
1回答
我开始学习近似算法，我正在读一本关于这方面的书，但我不理解集合覆盖算法的分析。
有人能解释一下引理2.3吗？它很短，但我不理解它。
浏览 1提问于2012-02-11得票数 0
回答已采纳
我正在写一个遗传算法来解决一类旅行商问题(TSP)。像标准的TSP一样，我的变体没有方向的概念。在标准的TSP中，由于需要形成一条返回起始城市的线路，因此对于任何最优解，都应该有两条相等的最优路线，即该线路周围的两条相反的路线。在遗传算法中，我会想象有时会出现相同(或相似)路径的好解决方案，但在不同的基因型中会以相反的方向编码。
浏览 0提问于2015-12-15得票数 1
1回答
我正在做以下练习:证明如果$P \neq NP$，则不存在背包问题(KP)的近似算法$A$，使得$\exists k \in \mathhbb{N}，\forall i \in S: OPT(I) -P_A(I) \leq k$其中$OPT(I)$是实例$I$上的最优利润，$P_A(I)$是$A$计算的利润。我知道对于KP有一个FPTAS $A'$，它保证在任何实例$I$和$\varepsilon > 0$上具有利润$P_{A'}(I) \geq (1 - \varepsilon)OPT<
浏览 2提问于2019-05-28得票数 0
1回答
根据iehrlich的评论(谢谢)，“调度”一词可能有误导性，这可能是一个更恰当的描述:给定一个矩阵N*N，找到一个将产生最大对角线和的行置换。( 1)我确实期望稳定匹配算法能够返回最优分配。有人能解释一下为什么失败吗？到目前为止，我最好的猜测是在不同的(作业，处理器)对之间存在联系。我也尝试了“稳定匹配与漠不关心”<e
浏览 2提问于2017-06-29得票数 5
回答已采纳
1回答
要执行的最大任务数
、、、、
我遇到了一个问题。我知道dp可以在这里应用，但不能实现。ith任务位于l[i]，需要执行t[i]时间。要执行ith任务，您必须到达l[i]点，并在该位置花费时间t[i]。给你T秒的时间，在这段时间里，你必须尽可能多地执行任务，然后回到开始的位置。我需要找出最大的时间可以执行T。考虑M= 3，T= 10，l[] = 1，2和t[] = 3，2。
如果我们执行第一项任务，所消耗的总时间是1(旅行)+3(完成任务)= 4，剩下的时间是10-4= 6
浏览 1提问于2021-07-05得票数 5
回答已采纳
2回答
最优页面替换算法
、、
我正在写一个程序，做3页替换算法。FIFO、LRU和OPT我假设这里是“按需”分页。我逐行解析文件并将其添加到类中，如下所示。这是我为其他两个算法所做的，需要逐行解析文件并提示输入帧大小。
浏览 5提问于2012-11-19得票数 0
5回答
分段最小二乘的动态规划算法
、、、、
几天来，我一直在尝试用Python实现这个算法。我不断地回到过去，然后放弃，变得沮丧。我不知道怎么回事。我没有任何人可以寻求帮助，也没有地方可以去寻求帮助，所以我来到了这里。现在算法开始于末尾(?)并且假设点p(x_i，y_i)是线段的一部分。然后注释说最优解是‘对于{p1，... pi−1}加上通过{pi，...pn}的(最佳)线的最优解’。现在最优的解决方案是这两条线段。
然后它进行了一个我不能理解的逻辑跳跃，并说：“假设最后一个点pn是从p_i开始的线段的一部分。如果Opt(j)表
浏览 2提问于2010-11-03得票数 10
1回答
置换的阶乘时间复杂度
、、、
我只想检查下面的代码是否具有阶乘时间复杂度。即O(n!)如果n是my_str中的字符数。据我所知，我可能漏掉了什么。 stack = list(a_str) while stack: new_results = [] for i in range(len(partial) + 1):
new_r
浏览 4提问于2021-12-21得票数 0
我正在阅读OAEP / PKCS填充，用于PGP将确定性算法从确定性加密转换为概率加密 (结果输出中的随机性)。这样，使用RSA加密的相同输入每次都会产生不同的输出。然而，维基百科用于概率加密的页面解决了一个看似简单的解决方案，但没有给出任何细节，说明它有什么问题：
将确定性加密方案转换为概率加密方案的一种直观方法是，在使用确定性算法加密之前，简单地用随机字符串填充明文相反，解密涉及应用确定性算法和忽略随机填充。然而，由于某些确定性加密方案的局限性，应用这种朴素方法的早期方案被打破。诸如最优非对
浏览 0提问于2016-05-24得票数 6
1回答
我的任务是证明这个问题不允许绝对逼近，即不可能有一个算法H，对于该问题的所有情形I，H(I) <= OPT(I) + k，其中OPT(I)是i的最优值，k是一个大于或等于1的数。通常的技巧是证明如果存在该算法，我们可以在多个时间内解决一些NP-困难问题。
有人知道哪一个问题可以用来解决这个问题吗？
浏览 0提问于2014-06-16得票数 1
回答已采纳
设P是A的置换。每次操作，我们都可以交换两个相邻顶点的值。是否有可能实现A = P，即在所有的1 <= i <= N中交换操作Ai = Pi。换句话说，每个顶点i在操作后都应该有值Pi。我试图将置换修改为q，其中Q1 < Q2 < ..这稍微改变了一个问题，即现在的最终状态应该是A1 < A2 <A3.一个。所以可以说，这个图能被排序吗？如果我的假设是错误的，请纠正我。
浏览 3提问于2022-02-11得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
