这个时间复杂度是多少?怎么算的?

来源:百度知道 编辑:UC知道 时间:2024/06/25 12:50:18
/******************
返回串中最长重复子串
******************/
#include "stdafx.h"
#include <iostream>
using namespace std;
char* getlongstr(char *str)
{
int max=0;
int len=strlen(str);
char* subs=new char[len+1];
memset(subs,0,sizeof(char)*(len+1));
for(int i=0;i<len;i++)
for(int j=i+1;j<len;j++)
{
if(str[i]==str[j])
{
int m=0,n=0;
for(m=i+1,n=1;m<j,n<=len-j;m++,n++)
if(str[m]!=str[j+n])
break;
if(m==j)
{
int sublen=j-i;
if(sublen>max)
{
max=sublen;
strncpy(subs,&str[i],sublen);
}
}
}
}
return subs;
}
int _tmain(int argc, _TCHAR* argv[])
{
char *str="cbabcdefacacbcdeabde";
//char *str="ababc";
char *p=getlongstr(str);
cout<<p<<endl;
return 0;
}

时间复杂度是根据算法最内层的表达式的运算次数计算的,
举个简单例子:
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
........
}
}
它的时间复杂度就是m*n
主要是把参与运算的表达式的运算次数加起来
像楼主提出的问题中,算法中包含了一个嵌套循环,所以时间复杂度应该是len的平方
恩,前面没看到,你后面的if语句中也有循环,那就要全部加起来

O(n^2)