我如何找到这段代码的时间和空间复杂性?
我很难找到这个代码的空间和时间复杂度,我写了一个字符串找到回文数。我如何找到这段代码的时间和空间复杂性?
/**
This program finds palindromes in a string.
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int checkPalin(char *str, int len)
{
int result = 0, loop;
for (loop = 0; loop < len/2; loop++)
{
if (*(str+loop) == *(str+((len - 1) - loop)))
result = 1;
else {
result = 0;
break;
}
}
return result;
}
int main()
{
char *string = "baaab4";
char *a, *palin;
int len = strlen(string), index = 0, fwd=0, count=0, LEN;
LEN = len;
while(fwd < (LEN-1))
{
a = string+fwd;
palin = (char*)malloc((len+1)*sizeof(char));
while(index<len)
{
sprintf(palin+index, "%c",*a);
index++;
a++;
if (index > 1) {
*(palin+index) = '\0';
count+=checkPalin(palin, index);
}
}
free(palin);
index = 0;
fwd++;
len--;
}
printf("Palindromes: %d\n", count);
return 0;
}
我给它一个镜头,这就是我想:
主,我们有两个while循环。外部字符串在字符串的整个长度-1上运行。现在这里是混淆,内部while循环首先遍历整个长度,然后是n-1,然后是n-2等,用于外部while循环的每次迭代。那么这意味着我们的时间复杂度将是O(n(n-1)) = O(n^2-n) = O(n^2)
? 而对于空间复杂性,最初我给字符串长度+1分配空间,然后(长度+ 1)-1,(长度+1)-2等,所以我们如何从中找到空间复杂度? 对于checkPalin函数,它的O(n/2)
。
我正在准备面试,并想了解这个概念。
谢谢
不要忘记,每次调用checkPalin(每次通过main内部循环执行操作)都会在checkPalin中执行循环index/2
次。除此之外,您对算法时间复杂性的计算是正确的。由于index
变得大到n
,这增加了另一个因素n
与时间复杂度,给出了O(n )。
至于空间强度,你分配每次通过外部循环,但然后释放它。所以空间复杂度是O(n)。 (注意O(n)== O(n/2),它只是指数和函数的形式,这很重要。)
对于时间复杂度,您的分析是正确的。由于n +(n-1)+(n-2)+ ... + 1步,它是O(n^2)。对于空间复杂性,您通常只计算任何给定时间所需的空间。在你的情况下,你需要的最多额外的内存是O(n)第一次通过循环,所以空间复杂度是线性的。
这就是说,这不是检查回文的特别好的代码。你可以在O(n)时间和O(1)空间中完成它,并且实际上有更清晰和更清晰的代码来启动。
Gah:没有仔细阅读。其他地方给出了正确的答案。
这段代码检查字符串中的多个回文,而不仅仅是一个。所以我们可以在一个字符串中包含n个回文。实质上,我从给定的字符串中创建子字符串,然后检查O(n/2)(通过checkPalin函数完成),如果这是一个回文。 – infinitloop 2011-05-02 16:25:50
我不明白这是如何在O(n)时间内完成的。一串n个相同的符号具有O(n^2)个回文(每个符号本身;每个连续的对;每个连续的3个串;等等)。我不知道(一般情况下)如何能够比它们的数量更快地计算出它们。 – 2011-05-02 16:31:20
特德是对的,基本上我们必须成对(至少这是我怎么想的),我们需要至少两个字符串来检查回文。 :) – infinitloop 2011-05-02 16:36:41
啊,我错过了。如果我错了,纠正我,所以时间复杂性应该写成这样:O(n(n-1(n/2)))= O(1/2(n^3-n^2))= O (N^3)。这很糟糕! – infinitloop 2011-05-02 16:32:17
@rashid - 我认为你修改后的分析是正确的。无论是不好还是不好,我都不知道。这是一个难以有效执行的难题。您可能可以将空间复杂度降低到O(1),而不会减慢算法速度;我不明白为什么你不能(只需要更多的簿记)只需检查就位,而不要将子字符串复制到划痕区域。 – 2011-05-02 16:45:00