所以有一种算法可以接收一个字符数组，例如"Alice likes Bob"并反转它，所以我们有了"Bob likes Alice"。以下是该算法的代码：
public static void reverseWords(char[] input) {
int n = input.length;
//First, reverse the whole string.
reverse(input, 0, n - 1);
//Second, Reverses each word in the string.
int start = 0, end = 0;
while (start < n) {
while (start < end || start < n && input[start] == ' ') {
++start; // Skip spaces chars.
}
while (end < start || end < n && input[end] != ' ') {
++end; // Skip non-spaces chars.
}
reverse(input, start, end - 1);
}
}
public static void reverse(char[] array, int start, int end){
while(start<end){
char tmp = array[start];
array[start++] = array[end];
array[end--] = tmp;
}
}
public static int find(char[] array, char c, int start) {
for (int i = start; i < array.length; i++) {
if (array[i] == c) {
return i;
}
}
return -1;
}
有人可以解释这段代码在 0(n( 时间内运行吗？还有函数查找的目的是什么？我看不到在任何地方被召唤。
显然你正在学习...但是你需要学会正确使用术语。
这个反向字符串算法的运行时间是多少？
运行时间是算法运行所需的时间。 显然，这取决于您运行它的硬件、编译器、您提供的输入......等等。 基本上，这不是一个有意义的问题。 如果你真的需要知道运行时间....你衡量它。
有人可以解释这段代码在 O(n( 时间内运行吗？
现在这是一个有意义的问题。 您不再询问运行时间：测量或估计。 您现在询问的是算法的计算复杂度度量。 这是关于分析代码以确定运行时间1如何根据问题的大小而变化;即输入。
是的，它O(N).
弄清楚为什么(非正式地(将代码的各个部分分解为更小的块，并弄清楚每个块在做什么，以及它将"触摸"(读取或写入(输入中的每个字符多少次。 然后将它们累加起来，得到一个代数"公式"。
这个公式f(n)看起来像C1 * n + C2吗？ 或者你能证明f(n)比一些C1 * n小n因为它变得非常大吗？
(我很确定我可以...但我会把细节留给你！
还有功能
find的目的是什么. 我没有看到find在任何地方被召唤。
这看起来像是书中的一个错误。
find方法的表面上目的是查找数组中出现给定字符的位置。 但正如你所说，它没有被使用。
将其归咎于写作/编辑/出版方面的质量控制不佳。 它发生了。
1 - 嗯...实际上不是真正的运行时间。 我们通常做的是计算作为运行时间的理论代理的东西;例如，读取和写入变量等原始操作。 这不会也不能为您提供实时的度量。 但由于复杂性分析的主要目的是在算法之间进行选择，因此这通常无关紧要。 当它发生时，您需要求助于测量和比较运行时间。