C 最长直线算法

Question

我想分析复制函数调用次数的最佳和最差情况。一般案例的难度是多少？请帮我理解这个解决方案？

我认为最好的情况是 1，最坏的情况是 n-1，对吗？

#include <stdio.h>
#define MAXLINE 1000 /* maximum input line size */
 
int get_line(char line[], int maxline);
void copy(char to[], char from[]); 
 
/* print longest input line */
int main() 
{
int es;
int len; /* current line length */
int max; /* maximum length seen so far */
char line[MAXLINE]; /* current input line */
char longest[MAXLINE]; /* longest line saved here */
es=0;
max = 0;
while ((len = get_line(line, MAXLINE)) > 0)
    if (len > max) 
    {
        es++;
        max = len;
        copy(longest, line);
    }
    printf("%d",es);
if (max> 0)  /* there was a line */
    printf("\nlongest is:%s\n", longest);
return 0;
}
 
/* get_line: read a line into s, return length */
int get_line(char s[], int lim)
{
int c, i;
 
 
for (i=0; i<lim-1 && (c=getchar()) !=EOF && c!='\n'; ++i)
    s[i] = c;
 
if (c == '\n')
{
    s[i] = c;
    ++i;
}
s[i] = '[=10=]';
return i;
}
 
/* copy: copy 'from' into 'to'; assume to is big enough */
void copy(char to[], char from[])
{
int i = 0;
while ((to[i] = from[i]) != '[=10=]')
    ++i;
}

Answer 1

最佳情况

如果第一个 get_line 调用 returns 是所有连续字符串中最长的字符串，则

copy(longest, line) 将只执行一次。对于这种情况，相对于 copy.

的时间复杂度为 O(1)

最坏的情况

如果下一行比上一行长，那么 copy(longest, line) 将被调用的次数与 while 循环中的迭代次数一样多。基本上，在这种情况下，时间复杂度为 O(n)，其中 n - 迭代次数。

平均情况

这个比较棘手，我知道如何计算它的上限。所以，我假设你的字符串的长度是均匀分布的并且都是不同的

因此，对于 n 次迭代，将有 n 种不同的长度，因此会有 n! 种可能的排列。对于一个案例，当在第 n 次迭代时达到最大值时，有 (n-1)! 种组合 -> 在 n 时达到最大值的概率是 (n-1)!/n! = 1/n。

现在，直到第 n 步达到最大值的次数为 1 + 1/2 + ... + 1/n ~ log(n)。如前所述，它是平均复杂度的上限，因为字符串的长度不一定是唯一的。

因此，相对于 copy 方法，时间复杂度为 O(log(n))。

C 最长直线算法

C longest line algorithm

c

algorithm

time-complexity

最佳情况

最坏的情况

平均情况