这种独特的字符串函数的执行时间是否从简单的O(n ^ 2)方法中减少了？

Question

推断字符串是否包含所有唯一字符(并且不使用任何其他数据结构)的通用算法表示要遍历字符串,针对搜索匹配的整个字符串迭代每个字母.这种方法是O(n ^ 2).

下面的方法(用C语言编写)使用偏移量来迭代字符串部分,因为例如在短字符串中没有理由用第一个字符作为第一个字符来测试最后一个字符.

我的问题是:算法的运行时间是O(n!)还是O(nlogn)？

#include <stdio.h>

int strunique(const char *str)
{
    size_t offset = 1;
    char *scout = (char *)str, *start;

    for (; *scout != '\0'; ++scout, ++offset)
        for (start = (char *)str + offset; *start != '\0'; ++start)
            if (*start == *scout)
                return 0;

    return 1;
}

int main(void)
{
    printf("%d\n", strunique("uniq"));
    printf("%d\n", strunique("repatee"));

    return 0;
}

Answer 1

除了其他答案之外,我想指出问题可以在O(1)没有额外内存的情况下解决,并且无需修改输入字符串的内容.

首先,做strnlen(str, 256).如果你得到超过255多,return 0.根据鸽子原则,某些角色必须不止一次出现.此操作仅O(1)在我们仅检查字符串的有界前缀时才需要.

现在,字符串比常量(256)短,因此使用任何朴素算法仅在O(1)额外的时间内完成.

Answer 2

不,它仍然是O(n ^ 2).你只是稍微提高了常量.你仍然需要做两个循环 - 基本上天真的计数循环测量大O时间的方式应该告诉你这个.

而且,没有O(n + 1/2n)这样的东西.Big O表示法是为了让您了解应该采取的数量级.n + 1/2n = 1.5n.由于大O掉落所有常数因子,那就是n.

你可以在没有额外内存的情况下击败O(n ^ 2).如果没有别的,您可以通过ascii值(nlog(n)time)对字符串进行排序,然后遍历数组,寻找du(n次)的O(n + nlogn)= O(nlogn)时间.可能还有其他技巧.

请注意,排序方法可能无法提供更好的运行时间 - 天真的方式具有1的最佳案例运行时,而排序第一算法必须排序,因此它具有nlogn的最佳情况.所以最好的大时间可能不是最好的选择.

Answer 3

简短的回答

如果数可能的字符(不要与混淆的字符串长度)是不固定的(不是这里的情况),你的算法的时间复杂度为O(N ^ 2) .如果我们假设只有固定数量的有效字符(在这种情况下为255/ 4G),则算法在最坏情况下运行O(n).如果条件成立,则可以容易地改进算法以在O(1)中运行.

注意渐近行为和大哦:这些是理论结果.这不是因为算法在O(1)中运行,它在合理的时间内运行.这意味着它在恒定的时间内运行.这样-渐近讲-无论你输入一个字符串,长度10是不会做出任何区别¹⁰⁰⁰或一个长度为10 ¹⁰⁰⁰⁰(假设这些长度足够大).它所花费的时间也可能超过宇宙年龄的一百倍.

说明

你可以在for循环上做一个简单而不是最坏情况的分析:

for (; *scout != '\0'; ++scout, ++offset)
    for (start = (char *)str + offset; *start != '\0'; ++start)
        //single statement

现在我们想知道单个语句(它包含固定数量的语句)将重复多少次.因为你永远不会修改字符串的内容.我们知道,有一个索引ñ在该值\0.

所以我们可以把它重写为:

for (scout = 0,offset = 0; scout < n; ++scout, ++offset)
    for (start = offset; *start < n; ++start)
        //single statement

(我假设字符串从内存地址开始0),但由于这只是一个允许的转换,因此只能简单地推理它.

现在我们将计算内for循环中的语句数(参数化).这相当于:

使用o的偏移量和n的长度.

现在我们可以使用这个公式来计算外for循环级别的指令数.这里o开始0并迭代(不包括)n.所以说明总数是:

哪个是O(n ^ 2).

但现在必须要问:是否有可能构建这样的字符串？答案是否定的!只有255有效字符(NUL字符不被视为字符); 如果我们不能做出这个假设,则上述成立.假设第一个字符是一个a(带有一个任意的char),那么它或者与a字符串中的另一个字符匹配,这可以在O(n)时间内解析(循环遍历字符串的其余部分); 或者它意味着所有其他字符都不同于a.在第一种情况下,算法终止于O(n); 在第二种情况下,这意味着第二个字符是不同的.

让我们说第二个角色是b.然后我们再次迭代O(n)中的字符串,如果它找到另一个,b我们在2n或O(n)步之后终止.如果没有,我们需要尝试找到下一个字符的匹配项c.

关键是我们只需要在大多数255时间执行此操作:因为只有255个有效字符.结果,时间复杂度为255n或O(n).

替代解释

这种解释的另一个变体是"如果外部for循环正在寻找第i个字符,我们知道i左边的所有字符都与该字符不同(否则我们之前就已经拒绝了)." 现在由于只有255字符,左边的所有字符彼此不同,而且当前字符不同,我们知道对于256字符串的第 - 个字符,我们再也找不到新的不同字符了,因为没有这样的字符.

例

假设你有一个字母3字符(a,b和c) -这只是为了更容易地了解此事.现在说我们有一个字符串:

scout
v
b a a a a a b
  ^
  start

很明显,您的算法将使用O(n)步骤:start将简单地迭代整个字符串一次,到达b并返回.

现在说b字符串中没有重复.在这种情况下,算法在迭代字符串一次后不会停止.但是这意味着所有其他字符应该与a不同(毕竟我们遍历字符串,并没有找到重复).所以现在考虑一个具有该条件的字符串:

scout
v
b a a a a a a
  ^
  start

现在很明显,第一次尝试b在字符串的其余部分中找到一个字符将会失败.现在你的算法增加了侦察:

  scout
  v
b a a a a a a
    ^
    start

并开始寻找a.我们非常幸运:第一个角色是a.但如果有重复a; 它最多需要两次迭代,所以O(2n)找到重复.

现在我们达到了约束的情况:也没有a.在这种情况下,我们知道字符串必须以

    scout
    v
b a c ...

我们进一步知道字符串的其余部分不能包含b's a',否则scout它将永远不会移动那么远.唯一剩下的可能性是字符串的其余部分包含c's'.所以字符串写道:

    scout
    v
b a c c c c c c c c c c
      ^
      start

这意味着在遍历字符串最多3次之后,无论字符串的大小如何,或者字符在该字符串中的分布方式,我们都会发现这样的重复.

将此修改为O(1)时间

您可以轻松修改此算法以使其在O(1)时间内运行:只需在索引上放置其他边界:

int strunique(const char *str)
{
    size_t offset = 1;
    char *scout = (char *)str, *start, *stop = scout+255;

    for (; scout < stop && *scout != '\0'; ++scout, ++offset)
        for (start = (char *)str + offset; start <= stop && *start != '\0'; ++start)
            if (*start == *scout)
                return 0;

    return 1;
}

在这种情况下,我们限制了第一个循环,使得它最多访问前255个字符,内循环仅访问前256个(注意<=而不是<).因此,总步数由255 x 256或O(1)限制.上面的解释已经证明了为什么这就足够了.

注意:如果这是C,你需要更换255的4'294'967'296,这使得它确实在理论上为O(n) ,但实际上是为O(n ^ 2)在这个意义上,之前的常数因子ñ是巨大的O(N)是Ø (n ^ 2)将胜过它.

由于我们将字符串终止检查与256-check 结合使用,因此该算法的运行速度几乎总是比上面提出的算法快.可能额外周期的唯一来源是随修改的for-loops 一起提供的附加测试.但由于这些会导致更快的终止,因此在许多情况下不会产生额外的时间.

大哦

可以说:" 是的,对于长度大于或等于256个字符的字符串都是如此. ","那些大小小于256？的字符串呢？".重点是大哦分析处理渐近行为.即使行为对于某些小于或等于某个长度的字符串是超指数的,也不要考虑这些.

更多地强调渐近行为的(有问题的)方面.可以说以下算法渐近正确:

int strunique(const char *str) {
    return 0;
}

它总是返回false; 因为"长度为n ₀,因此对于每个输入长度n> n _0,此算法将返回正确的结果." 这与big-oh本身没什么关系,更多的是要说明一个人必须小心,说O(1)中运行的算法将胜过O(n ^ 6)中任何合理输入的算法.有时,常数因素可能是巨大的.

Answer 4

你的算法是O(N^2).通过简单地注意到在最坏的情况下,一个包含所有唯一字符的字符串,每个字符必须与其后面的每个字符进行检查,这很容易.也就是说,最糟糕的情况是N*(N-1)/2 = O(N^2)比较.

请注意,根据定义:

f(x) = O(g(x))

如果存在某种常数,那么|f(x)| <= M|g(x)|对于所有足够大的常数x.所以,当你说f(x) = O(n + 1/2n)(对你的算法不正确)时,接下来是:

  f(x) = O(n + 1/2n)
  f(x) <= M * (n + 1/2n) for some M, n_0 for n >= n_0, by definition
  f(x) <= (3/2 * M) n, n >= n_0
  f(x) <= M' n, setting M' = 3/2 M, n >= n_0
  f(x) = O(n), by definition

也就是说,常量总是会丢失,这就是为什么你可能会听到常量无关紧要的表达式(至少就计算运行时复杂性而言 - 显然它们对实际性能很重要)