这段代码的时间复杂度是多少？ [英] What would be the time complexity of this code?

问题描述

问题是：

1.给定两个字符串A，B（A小于B）找到A中的A或A的任何排列的索引。



例如>



A：用于

B：dforfdorfaaabrofasdf



ans：1,6,13

The problem is:
1. given two string A, B (A less than B in size) find the indexes at which A or any permutation of A occurs in B.

e.g>

A : for
B : dforfdorfaaabrofasdf

ans : 1,6,13

#include<iostream.h>
using namespace std;
#include<conio.h>

int main()
{
    char s[100],t[100];
    int i,j,k,l,flag;
    gets(s);
    gets(t);
    int sums,sumt;
    int lens=strlen(s);
    int lent=strlen(t);
    for(i=0;i<lent;i++)
    sumt+=t[i];
    for(i=0;i<lens;i++)
    {
        sums=0;
        for(j=i;j<i+lent;j++)
        sums+=s[j];
        if(sums==sumt)
        {
            for(k=0;k<lent;k++)
            {
                for(l=0;l<lent;l++)
                {
                    flag=0;
                    if(s[i+k]==t[l])
                    {
                        flag=1;
                        break;
                    }
                }
                if(!flag)
                break;
            }
            if(flag)
            {
                printf("%d\t",i);
                i=i+lent-1;
            }
        }
    }
    getch();
}

推荐答案

如果它是你老师的家庭作业，你应该考虑一下并学点东西。



如果没有，你得到的评论是正确的：这是一个糟糕的算法。 ; - ）

if it is a homework from your teachers you should think about it and learn something.

If not, the comment you got are right: it is a bad algorithm. ;-)

因为你有两个循环超过字符串 A 和一个字符串 B ，简单的答案是 O（a²* b）其中 a 是第一个字符串的长度 b 另一个字符串的长度。



实际上，它应该接近 O（a * b）对于随机字符串，因为在这种情况下总和不应该经常匹配。



最坏的情况是在 abeabeacd 中搜索 acd ，因为总和通常会匹配，但字母不同。



如果较短的单词中允许重复的字母，算法将无效。

Since you have 2 loops over string A and one over string B, the easy answer would be O(a² * b) where a is the length of first string and b the length of the other string.

In practice, it should be near to O(a * b) for random strings as the sum should not match often in that case.

The worst case would be to search for acd in abeabeacd as the sum will often match but with different letters.

Also the algorithm won't works if duplicate letters are allowed in the shorter word.

这篇关于这段代码的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！