这个独特的字符串函数的执行时间是否比原始的 O(n^2) 方法减少了？
Is the execution time of this unique string function reduced from the naive O(n^2) approach?
推断字符串是否包含所有唯一字符（并且不使用任何其他数据结构）的通用算法表示遍历字符串，针对整个字符串迭代每个字母以搜索匹配项。这种方法是 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 != '[=10=]'; ++scout, ++offset)
for (start = (char *)str + offset; *start != '[=10=]'; ++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)这样的东西。大 O 表示法是让您了解某些东西应该采用的数量级。 n+1/2n=1.5n。由于大 O 删除了所有常量因子，所以它就是 n。
虽然你可以在没有额外内存的情况下击败 O(n^2)。如果不出意外，您可以按 ascii 值（nlog(n) 时间）对字符串进行排序，然后在 O(n+nlogn)=O(nlogn) 时间内遍历数组以查找重复项（n 时间）。可能还有其他技巧。
请注意，尽管排序方法可能不会提供更好的运行时间 - 朴素方法的最佳情况运行时间为 1，而排序优先算法必须进行排序，因此它的最佳情况为 nlogn。所以最好的big-O时间未必是最好的选择。
你的算法是O(N^2)。这很容易，只需注意在最坏的情况下，一个包含所有唯一字符的字符串，每个字符都必须对照它后面的每个字符进行检查。也就是说，最坏情况下，N*(N-1)/2 = O(N^2) 比较。
注意 by definition:
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
也就是说，常量总是会丢失，这就是为什么您可能会听到常量无关紧要的表达（至少就计算运行时复杂度而言 - 显然它们对实际性能很重要）
除了其他答案，我想指出的是，这个问题可以在O(1)中解决，不需要额外的内存，也不需要修改输入字符串的内容。
首先，做strnlen(str, 256)。如果你得到超过 255，return 0。根据鸽巢原理，某些字符必须出现不止一次。此操作仅需要 O(1)，因为我们只检查字符串的有界前缀。
现在，字符串比常量 (256) 短，因此使用任何朴素算法仅需 O(1) 额外时间即可完成。
包含所有唯一字符的字符串的长度最多为 255。在这种情况下，您的算法运行时间为 O(1)。
如果字符串包含重复字符，则其中一个重复字符会出现在字符串的前 255 个元素中。那么最坏的情况就是字符串的前 254 个字符是唯一的，第 255 个字符重复，直到字符串结束。然后你的算法在 O(N) 时间内运行。
您可以通过首先检查字符串的长度是否大于 255 并在大于 255 时立即失败来保证算法的 O(1) 时间。
所有这些都是假设 char 取 256 个值之一。如果将 char 中的字符数视为变量 C，则在字符串仅包含唯一字符的情况下算法的复杂度为 O(C^2)，在字符串仅包含唯一字符的情况下为 O(NC)包含重复项，您可以通过首先检查字符串的长度不大于 C 来保证 O(C^2) 时间。
最佳算法是 O(min(N, C))，首先检查字符串不长于 C，然后使用任何线性时间重复检测算法。
简答
如果 个 可能的字符 （不要与 字符串的长度 混淆）不是fixed（这里不是这种情况）你算法的时间复杂度是O(n^2)。 如果我们假设只有固定数量的有效字符（在本例中为 255/4G），您的算法 运行 worst-caseO(n)。如果 条件成立 ，则算法可以很容易地 改进为 运行 O(1).
Note on asymptotic behavior and big-oh: these are theoretical results. It's not because an algorithm runs in O(1), it runs in reasonable time. It means it runs in constant time. So that - asymptotically speaking - it won't make any difference whether you enter a string with length 101000 or one with length 1010'000 (given these lengths are large enough). The time it takes can be more than one hundred times the age of the universe as well.
说明
您可以对 for 循环进行 比 worst-case 更简单的分析：
for (; *scout != '[=10=]'; ++scout, ++offset)
for (start = (char *)str + offset; *start != '[=10=]'; ++start)
//single statement
现在我们想知道单个语句（它包含固定数量的语句）将被重复多少次。因为您从不 修改 字符串的内容。我们知道有一个索引 n 处的值为 [=21=].
所以我们可以改写为：
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（带有任意字符），那么它要么与字符串中的另一个 a 匹配，这可以在 O(n) 时间（遍历字符串的剩余部分）；或者这意味着所有其他字符 不同于 a。在第一种情况下，算法在 O(n) 时终止；在第二种情况下，这意味着第二个字符不同。
假设第二个字符是b。然后我们再次遍历 O(n) 中的字符串，如果它找到另一个 b 我们终止，在 2n 或 O(n) 步。如果不是，我们需要尝试找到下一个字符的匹配项 c.
关键是我们只需要这样做最多255次：因为只有255个有效字符.因此，时间复杂度为 255n 或 O(n).
替代解释
这个解释的另一个变体是”如果外for循环正在寻找i-th字符，我们知道i左边的所有字符都不同于那个字符（否则我们早就拒绝了）。" 现在因为只有 255 个字符，并且左边的所有字符彼此和当前字符都不同，我们知道对于256-字符串的第一个字符，我们找不到新的不同字符了，因为没有这样的字符。
例子
假设您有一个包含 3 个字符（a、b 和 c）的字母表 - 这只是为了更容易理解这件事。现在假设我们有一个字符串：
scout
v
b a a a a a b
^
start
很明显，您的算法将使用 O(n) 个步骤：start 将简单地遍历整个字符串一次，达到 b和 return.
现在假设字符串中没有 b 的重复项。在这种情况下，算法不会在遍历字符串一次后停止。但这意味着所有其他字符都应该与 a 不同（毕竟我们已经遍历了字符串，并且没有找到重复项）。所以现在考虑具有该条件的字符串：
scout
v
b a a a a a a
^
start
现在很明显，第一次尝试在字符串的剩余部分中查找字符 b 将会失败。现在你的算法递增 scout:
scout
v
b a a a a a a
^
start
并开始搜索 a。在这里我们很幸运：第一个字符是 a。但是如果有重复的a；它最多需要两次迭代，所以 O(2n) 找到重复项。
现在我们遇到了边界情况：也没有 a。在这种情况下，我们知道字符串必须以
开头
scout
v
b a c ...
我们还知道字符串的其余部分不能包含 b 或 a，否则 scout 永远不会移动那么远。唯一剩下的可能性是字符串的其余部分包含 c。所以字符串读取
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 != '[=17=]'; ++scout, ++offset)
for (start = (char *)str + offset; start <= stop && *start != '[=17=]'; ++start)
if (*start == *scout)
return 0;
return 1;
}
在这种情况下，我们限制了第一个循环，使其最多访问 前 255 个字符，内部循环仅访问第一个 256（注意 <= 而不是 <）。所以总步数受限于 255 x 256 或 O(1)。上面的解释已经说明了为什么这是足够的。
Note: In case this is C, you need to replace 255 by 4'294'967'296 which makes it indeed theoretically O(n), but practically O(n^2) in the sense that the constant factor before the n is that huge for O(n) that O(n^2) will outperform it.
由于我们将字符串终止检查与 256-检查相结合，因此该算法 运行 几乎总是比上面提出的算法更快。潜在额外循环的唯一来源是修改后的 for 循环附带的额外测试。但由于这些会导致更快的终止，因此在许多情况下不会导致额外的时间。
Big-oh
可以说：“是的，对于长度大于或等于 256 个字符的字符串也是如此。”，“对于长度小于 [=38= 的字符串呢？ ]？”。重点是 big-oh 分析处理渐近行为 。即使某些小于或等于特定长度的字符串的行为是 super-exponential，您也不会考虑这些。
更多地强调渐近行为的（有问题的）方面。可以说以下算法渐近地是正确的：
int strunique(const char *str) {
return 0;
}
它总是 return 是错误的；因为 " 有一个长度 n0 这样对于每个输入长度 n > n0 这个算法将 return 正确的结果。" 这与big-oh 本身没有太大关系，更多的是说明在 中说算法运行ning 一定要小心对于任何合理的输入，O(1) 将优于 O(n^6) 中的算法。有时常数因子可能很大。
推断字符串是否包含所有唯一字符（并且不使用任何其他数据结构）的通用算法表示遍历字符串，针对整个字符串迭代每个字母以搜索匹配项。这种方法是 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 != '[=10=]'; ++scout, ++offset)
for (start = (char *)str + offset; *start != '[=10=]'; ++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)这样的东西。大 O 表示法是让您了解某些东西应该采用的数量级。 n+1/2n=1.5n。由于大 O 删除了所有常量因子，所以它就是 n。
虽然你可以在没有额外内存的情况下击败 O(n^2)。如果不出意外，您可以按 ascii 值（nlog(n) 时间）对字符串进行排序，然后在 O(n+nlogn)=O(nlogn) 时间内遍历数组以查找重复项（n 时间）。可能还有其他技巧。
请注意，尽管排序方法可能不会提供更好的运行时间 - 朴素方法的最佳情况运行时间为 1，而排序优先算法必须进行排序，因此它的最佳情况为 nlogn。所以最好的big-O时间未必是最好的选择。
你的算法是O(N^2)。这很容易，只需注意在最坏的情况下，一个包含所有唯一字符的字符串，每个字符都必须对照它后面的每个字符进行检查。也就是说，最坏情况下，N*(N-1)/2 = O(N^2) 比较。
注意 by definition:
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
也就是说，常量总是会丢失，这就是为什么您可能会听到常量无关紧要的表达（至少就计算运行时复杂度而言 - 显然它们对实际性能很重要）
除了其他答案，我想指出的是，这个问题可以在O(1)中解决，不需要额外的内存，也不需要修改输入字符串的内容。
首先，做strnlen(str, 256)。如果你得到超过 255，return 0。根据鸽巢原理，某些字符必须出现不止一次。此操作仅需要 O(1)，因为我们只检查字符串的有界前缀。
现在，字符串比常量 (256) 短，因此使用任何朴素算法仅需 O(1) 额外时间即可完成。
包含所有唯一字符的字符串的长度最多为 255。在这种情况下，您的算法运行时间为 O(1)。
如果字符串包含重复字符，则其中一个重复字符会出现在字符串的前 255 个元素中。那么最坏的情况就是字符串的前 254 个字符是唯一的，第 255 个字符重复，直到字符串结束。然后你的算法在 O(N) 时间内运行。
您可以通过首先检查字符串的长度是否大于 255 并在大于 255 时立即失败来保证算法的 O(1) 时间。
所有这些都是假设 char 取 256 个值之一。如果将 char 中的字符数视为变量 C，则在字符串仅包含唯一字符的情况下算法的复杂度为 O(C^2)，在字符串仅包含唯一字符的情况下为 O(NC)包含重复项，您可以通过首先检查字符串的长度不大于 C 来保证 O(C^2) 时间。
最佳算法是 O(min(N, C))，首先检查字符串不长于 C，然后使用任何线性时间重复检测算法。
简答
如果 个 可能的字符 （不要与 字符串的长度 混淆）不是fixed（这里不是这种情况）你算法的时间复杂度是O(n^2)。 如果我们假设只有固定数量的有效字符（在本例中为 255/4G），您的算法 运行 worst-caseO(n)。如果 条件成立 ，则算法可以很容易地 改进为 运行 O(1).
Note on asymptotic behavior and big-oh: these are theoretical results. It's not because an algorithm runs in O(1), it runs in reasonable time. It means it runs in constant time. So that - asymptotically speaking - it won't make any difference whether you enter a string with length 101000 or one with length 1010'000 (given these lengths are large enough). The time it takes can be more than one hundred times the age of the universe as well.
说明
您可以对 for 循环进行 比 worst-case 更简单的分析：
for (; *scout != '[=10=]'; ++scout, ++offset)
for (start = (char *)str + offset; *start != '[=10=]'; ++start)
//single statement
现在我们想知道单个语句（它包含固定数量的语句）将被重复多少次。因为您从不 修改 字符串的内容。我们知道有一个索引 n 处的值为 [=21=].
所以我们可以改写为：
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（带有任意字符），那么它要么与字符串中的另一个 a 匹配，这可以在 O(n) 时间（遍历字符串的剩余部分）；或者这意味着所有其他字符 不同于 a。在第一种情况下，算法在 O(n) 时终止；在第二种情况下，这意味着第二个字符不同。
假设第二个字符是b。然后我们再次遍历 O(n) 中的字符串，如果它找到另一个 b 我们终止，在 2n 或 O(n) 步。如果不是，我们需要尝试找到下一个字符的匹配项 c.
关键是我们只需要这样做最多255次：因为只有255个有效字符.因此，时间复杂度为 255n 或 O(n).
替代解释
这个解释的另一个变体是”如果外for循环正在寻找i-th字符，我们知道i左边的所有字符都不同于那个字符（否则我们早就拒绝了）。" 现在因为只有 255 个字符，并且左边的所有字符彼此和当前字符都不同，我们知道对于256-字符串的第一个字符，我们找不到新的不同字符了，因为没有这样的字符。
例子
假设您有一个包含 3 个字符（a、b 和 c）的字母表 - 这只是为了更容易理解这件事。现在假设我们有一个字符串：
scout
v
b a a a a a b
^
start
很明显，您的算法将使用 O(n) 个步骤：start 将简单地遍历整个字符串一次，达到 b和 return.
现在假设字符串中没有 b 的重复项。在这种情况下，算法不会在遍历字符串一次后停止。但这意味着所有其他字符都应该与 a 不同（毕竟我们已经遍历了字符串，并且没有找到重复项）。所以现在考虑具有该条件的字符串：
scout
v
b a a a a a a
^
start
现在很明显，第一次尝试在字符串的剩余部分中查找字符 b 将会失败。现在你的算法递增 scout:
scout
v
b a a a a a a
^
start
并开始搜索 a。在这里我们很幸运：第一个字符是 a。但是如果有重复的a；它最多需要两次迭代，所以 O(2n) 找到重复项。
现在我们遇到了边界情况：也没有 a。在这种情况下，我们知道字符串必须以
scout
v
b a c ...
我们还知道字符串的其余部分不能包含 b 或 a，否则 scout 永远不会移动那么远。唯一剩下的可能性是字符串的其余部分包含 c。所以字符串读取
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 != '[=17=]'; ++scout, ++offset)
for (start = (char *)str + offset; start <= stop && *start != '[=17=]'; ++start)
if (*start == *scout)
return 0;
return 1;
}
在这种情况下，我们限制了第一个循环，使其最多访问 前 255 个字符，内部循环仅访问第一个 256（注意 <= 而不是 <）。所以总步数受限于 255 x 256 或 O(1)。上面的解释已经说明了为什么这是足够的。
Note: In case this is
C, you need to replace255by4'294'967'296which makes it indeed theoretically O(n), but practically O(n^2) in the sense that the constant factor before the n is that huge for O(n) that O(n^2) will outperform it.
由于我们将字符串终止检查与 256-检查相结合，因此该算法 运行 几乎总是比上面提出的算法更快。潜在额外循环的唯一来源是修改后的 for 循环附带的额外测试。但由于这些会导致更快的终止，因此在许多情况下不会导致额外的时间。
Big-oh
可以说：“是的，对于长度大于或等于 256 个字符的字符串也是如此。”，“对于长度小于 [=38= 的字符串呢？ ]？”。重点是 big-oh 分析处理渐近行为 。即使某些小于或等于特定长度的字符串的行为是 super-exponential，您也不会考虑这些。
更多地强调渐近行为的（有问题的）方面。可以说以下算法渐近地是正确的：
int strunique(const char *str) {
return 0;
}
它总是 return 是错误的；因为 " 有一个长度 n0 这样对于每个输入长度 n > n0 这个算法将 return 正确的结果。" 这与big-oh 本身没有太大关系，更多的是说明在 中说算法运行ning 一定要小心对于任何合理的输入，O(1) 将优于 O(n^6) 中的算法。有时常数因子可能很大。