标签: computer-science

我需要找到 n 的递归解，如果T(n)=3T(n/2)+nn>1 和 T(n)=1，则为2 的幂，否则。

使用替换n=2^m,S(m)=T(2^(m-1))I 可以归结为：

S(m)=2^m+3*2^(m-1)+3^2*2^(m-2)+?+3^(m-1) 2^1+3^m

但我不知道如何简单地做到这一点。

有人可以告诉我多处理和并行处理之间的确切区别吗？我有点困惑。感谢您的帮助。

我需要证明或反驳以下正则表达式

(RS + R )* R = R (SR + R)*
// or, for programmers:
/(RS|R)*R/ == /R(SR|R)*/

我有一种强烈的直觉，认为它们是等价的，但是我如何使用 REGEX 定律给出一步一步的证明。

通常，计算中缀数学表达式的程序使用调车场算法的一些变体首先将表达式转换为逆波兰表示法，然后计算逆波兰表示法以获得单个最终值。

我的问题是，是否有一些众所周知的算法绕过 INFIX -> RPN 步骤，并使用某种递归下降解析来评估初始中缀表达式？

据推测，在编写编译器或解析器来翻译 INFIX -> RPN 时可能很有用。RPN 是表达式（AST）的“编译形式”，它可以更容易地由计算机使用简单的输出堆栈进行评估。但是，如果您只是简单地编写将中缀表达式立即转换为数字输出值的代码，那么您可能无法缓存中间 RPN 形式。

那么，是否有任何众所周知的算法来解析中缀表达式而不先转换为 RPN？或者转换为 RPN 通常比任何其他方法更有效？

本地这个词是什么意思？例如，“您可以在本地运行它吗”和“您可以在本地登录吗？” 与在开发环境中做同样的事情相比。

例如，array a[]= {1,1,10}我们需要找到|x-1|+|x-1|+|x-10|最小的“x” 。
在这里，x 是 1。

它可以用贪婪的方法解决吗，比如取平均值或其他什么？
注意：取平均值不起作用，为什么？

我只能想出O(nlogn)解决方案（二进制搜索），还有其他方法如 dp 吗？

提前致谢！

我发现很难理解局部和全局未命中率之间的差异以及如何计算内存访问的平均时间，我只想举一个我试图解决的问题的例子。如果有人能告诉我我是否在正确的轨道上，或者我是否错了我错过的东西，我将不胜感激。

考虑以下多级缓存层次结构及其寻道时间和未命中率：

• L1 缓存，0.5 ns，20%
• L2 缓存，1.8 ns，5%
• L3 缓存，4.2 ns，1.5%
• 主存储器，70 ns，0%

在这种情况下，给出的寻道时间是指检查请求的数据在当前层次结构上是否可用，并将数据传输到上层（或 CPU）所需的总时间。这和命中时间一样吧？给出的未命中率是本地的。正如我所理解的，一个级别的未命中率需要乘以所有先前级别的未命中率才能对该级别进行正确处理。

假设我们有 1000 次内存访问，在 L1 中，其中 20% 会丢失。因此，其中 20% 将进入 L2，其中 5% 将错过。因此，从 1000 次内存访问中，1000 * 20% * 5% 将到达那里。现在，据我所知......如果我错了，请纠正我，上述未命中率是局部的，但它们的乘积是每个相应级别的全局未命中率。这意味着 L2 的全局未命中率为 0,2*0,05 = 1%。

现在，我可能对这个计算非常错误，但这就是我的想法：

AMAT (Average Memory Access Time) = Hit time + Miss rate * Miss penalty

AMAT = 0.5 + 0.2 * (1.8 + 0.2 * 0.05 * (4.2 + 0.2 * 0.05 * 0.015 * 70))

计算后我得到 AMAT = 0.868421 ns …

我想要编码的是，如果我输入camelcase，它应该只打印出camelcase，但是如果包含任何大写字母，例如，如果我输入camelCase，它应该打印出camel_case。

下面是我正在研究的一个，但问题是，如果我输入camelCase，它会打印出来camel_ase。

有人可以告诉我原因以及如何解决吗？

#include <stdio.h>
#include <ctype.h>

int main() {
    char ch;
    char input[100];
    int i = 0;

    while ((ch = getchar()) != EOF) {
        input[i] = ch;
        if (isupper(input[i])) {
            input[i] = '_';
            //input[i+1] = tolower(ch);
        } else {
            input[i] = ch;
        }
        printf("%c", input[i]);

        i++;
    }
}

在无向图 G=(V,E) 中，顶点被着色为红色、黄色或绿色。此外，存在一种将图划分为两个子集的方法，使得 |V1|=|V2| 或 |V1|=|V2|+1 其中以下条件适用：V1 的每个顶点都连接到 V2 的每个顶点，或者 V1 的顶点没有连接到 V2 的顶点。这递归地适用于 V1 和 V2 的所有诱导子图

我可以通过将邻接矩阵与其自身相乘三倍并逐步增加与主对角线的非零条目相对应的节点来找到图中的所有三角形。然后我可以查看三角形的节点是否以正确的方式着色。O(n^~2,8)！但是考虑到图形的独特属性，我想使用分治法找到一个解决方案来找到彩色三角形。这是具有给定属性的示例图。我需要找到粗体三角形： 蓝色框表示分区完全连接，紫色框表示分区之间没有连接

我想知道具有指数最坏时间复杂度的算法是否应该始终将其声明为 O(2^n)。例如，如果我有一个算法，对于输入大小的每一次增加，它的运算次数为三倍，我会将它的时间复杂度写为 O(3^n)，还是仍将其归类为 O(2^n)。

任何正式的解释将不胜感激。