这种独特的字符串函数的执行时间是否从简单的O(n ^ 2)方法中减少了?
推断字符串是否包含所有唯一字符(并且不使用任何其他数据结构)的通用算法表示要遍历字符串,针对搜索匹配的整个字符串迭代每个字母。 这种方法是O(n ^ 2) 。
下面的方法(用C语言编写)使用偏移量来迭代字符串部分,因为例如在短字符串中没有理由用第一个字符作为第一个字符测试最后一个字符。
我的问题是:算法的运行时间是O(n!)还是O(nlogn) ?
#include 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; }
不,它仍然是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的最佳情况。 所以最好的大时间可能不是最好的选择。
除了其他答案之外,我想指出问题可以在O(1)
解决而无需额外的内存,也无需修改输入字符串的内容。
首先,做strnlen(str, 256)
。 如果超过255,则return 0
。 根据鸽子原则,一些角色必须不止一次出现。 此操作仅采用O(1)
因为我们只检查字符串的有界前缀。
现在,字符串比常量(256)短,因此使用任何朴素算法仅在O(1)
额外时间内完成。
简短的回答
如果可能的字符数 (不要与字符串的长度混淆)不固定 (这里不是这种情况),算法的时间复杂度为O(n ^ 2) 。 如果我们假设只有固定数量的有效字符 (在本例中为255
/ 4G
),则算法在最坏情况下运行O(n) 。 如果条件成立 ,则可以容易地改进算法以在O(1)中运行 。
关于渐近行为和大哦的注意事项 :这些是理论结果。 这不是因为算法在O(1)中运行,它在合理的时间内运行。 这意味着它会在恒定的时间内运行。 所以 – 渐近地说 – 无论你输入长度为10 1000的字符串还是长度为10 10 000的字符串(假设这些长度足够大),它都没有任何区别。 它所花费的时间也可能超过宇宙年龄的一百倍。
说明
你可以对for循环进行简单而不是最坏情况的分析:
for (; *scout != '\0'; ++scout, ++offset) for (start = (char *)str + offset; *start != '\0'; ++start) //single statement
现在我们想知道单个语句(它包含固定数量的语句)将重复多少次。 因为你永远不会修改字符串的内容。 我们知道有一个索引n ,其值为\0
。
所以我们可以将它重写为:
for (scout = 0,offset = 0; scout < n; ++scout, ++offset) for (start = offset; *start < n; ++start) //single statement
(我假设字符串从内存地址0
开始),但由于这只是一个转换,允许,它只是简单地推理这个。
现在我们将计算内部for
循环(参数化)中的语句数。 这相当于:
使用o的偏移量和n的长度。
现在我们可以使用这个公式计算外部for
-loop级别的指令数。 这里o从0
开始并迭代(不包括) n
。 所以说明总数是:
哪个是O(n ^ 2) 。
但现在必须要问: 是否有可能构建这样的字符串 ? 答案是否定的 ! 只有255
有效字符( NUL
字符不被视为字符); 如果我们不能做出这个假设,则上述成立。 假设第一个字符是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 baaaaab ^ start
很明显,你的算法将使用O(n)步骤: start
将简单地迭代整个字符串一次,到达b
并返回。
现在说字符串中没有b
重复。 在这种情况下,算法在迭代字符串一次后不会停止。 但这意味着所有其他字符应该与a不同(毕竟我们已经迭代了字符串,并没有找到重复)。 所以现在考虑一个具有该条件的字符串:
scout v baaaaaa ^ start
现在很清楚,在字符串的其余部分中找到字符b
的第一次尝试将失败。 现在你的算法增加了侦察:
scout v baaaaaa ^ start
并开始寻找a
。 我们非常幸运:第一个角色是a
。 但是如果有重复a
; 它最多需要两次迭代,所以O(2n)找到重复。
现在我们已达到约束的情况:两者都没有。 在这种情况下,我们知道字符串必须以
scout v bac ...
我们进一步知道字符串的其余部分不能包含b
和s,因为否则scout
就不会移动那么远。 唯一剩下的可能性是字符串的其余部分包含c
。 所以字符串写道:
scout v bacccccccccc ^ 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)限制 。 上面的解释已经certificate了为什么这就足够了。
注意 :如果这是
C
,你需要用4'294'967'296
代替255
,这使得它理论上确实是O(n) ,但实际上是O(n ^ 2) ,因为n之前的常数因子是对于O(n)而言 , O(n ^ 2)将胜过它。
由于我们将字符串终止检查与256
检查结合起来,因此该算法的运行速度几乎总是比上面提出的算法快。 可能额外周期的唯一来源是随修改的for
-loops一起提供的附加测试。 但由于这些会导致更快的终止,因此在许多情况下不会导致额外的时间。
大哦
可以说:“ 是的,对于长度大于或等于256个字符的字符串都是如此。 ”,“那么大小小于256
字符串呢?”。 重点是大哦分析处理渐近行为 。 即使行为对于某些小于或等于某个长度的字符串是超指数的,也不要考虑这些。
强调渐近行为的(有问题的)方面更多。 可以说,以下算法渐近地说是正确的:
int strunique(const char *str) { return 0; }
它总是返回false; 因为“长度为n 0 ,因此对于每个输入长度n> n 0,此算法将返回正确的结果。” 这与big-oh本身没什么关系,更多的是要说明一个人必须小心说,在O(1)中运行的算法在O(n ^ 6)中优于任何合理输入的算法。 有时,常数因素可能是巨大的。
你的算法是O(N^2)
。 通过简单地注意到在最坏的情况下,一个包含所有唯一字符的字符串,每个字符必须与其后面的每个字符进行检查,这很容易。 也就是说,最坏情况下, N*(N-1)/2 = O(N^2)
比较。
请注意, 根据定义 :
f(x) = O(g(x))
如果存在一些常数,使得|f(x)| <= M|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
也就是说,常量总是会丢失,这就是为什么你可能会听到常量无关紧要的表达式(至少就计算运行时复杂性而言 - 显然它们对实际性能很重要)
包含所有唯一字符的字符串的长度最多为255.在这种情况下,算法将在O(1)时间内运行。
如果字符串包含重复的字符,则字符串的前255个元素中将出现其中一个重复字符。 然后最坏的情况是字符串的前254个字符是唯一的,并且第255个字符重复直到字符串的结尾。 然后你的算法在O(N)时间内运行。
通过首先检查字符串的长度是否大于255并且如果是,则立即失败,可以保证算法的O(1)时间。
所有这些都假设char
采用256个值中的一个。 如果将char
中的char
视为变量C,则在字符串仅包含唯一字符的情况下,算法的复杂度为O(C ^ 2),在字符串包含重复项的情况下为O(NC),并且你可以通过首先检查字符串的长度是否大于C来保证O(C ^ 2)时间。
最优算法是O(min(N,C)),首先检查字符串是否不长于C,然后使用任何线性时间重复检测算法。