کاهش مرتبه اجرایی

[imanrasekh]

سلام
من یک برنامه خیلی ساده دارم که مرتبه اجراییش O(mn) هست چون تابع استفاده شده دو حلقه وابسته داره
ولی باید مرتبه اجراییش رو به مرتبه خطی O(n) برسونم
میشه لطفا کمکم کنید



#include <iostream.h>
#include<stdlib.h>
int *char_count( const char* DNA, const int *starts, const int *ends, char letter);
int main()
{
char string[40]="ACGAAAAGGGTGCGCCGGGGACTGGGGGTAT";
const int enda[6]={3,10,13,16,20,23};
const int starta[6]={1,2,9,12,15,18} ;
int *counta=new int [6];
cout<<"number of occurrance of nucelotid in each interval is: \n";

counta= char_count(string,starta,enda,'G') ;
for(int m=0 ;m<=5;m++)
cout<<counta[m]<<"\t";
delete [] counta;
getch();
return 0;
}
//******************
int *char_count( const char* DNA, const int *starts, const int *ends, char letter)
{
int *count=new int [6];
for(int l=0;l<=5;l++)
{
count[l]=0;
for (int i=starts[l];i<= ends[l]; i++)
if(DNA[i] == letter)
count[l] ++ ;
}
return count;
}

[a.r.khoshghalb]

شما کد یه الگوریتم (O(nm رو می خوای بکنی (O(n ؟؟
باید الگوریتم عوض بشه! بگو سوال چیه و الگوریتمی که استفاده کردی چیه.

[imanrasekh]

خیلی ساده است
"تعداد دفعات تکرار کراکتر G در زیر رشته های یک رشته"
ولی باید بدون حلقه تو در تو اجراش کنم
ممنون

[a.r.khoshghalb]

راه درست و سریعش اینه که یک بار از اول رشته تا آخر رو بری، هر جا کاراکتر G دیدی، بشمری چند تا زیر رشته هستند که این کاراکتر رو دارند.
به این صورت : فرض کن خونه i اوم رشته ات G هست و می خوایم ببینیم چند تا زیر رشته هستند که خونه i اوم رو دارند.
به این صورت محاسبه می شود :

i * (n-i-1)

[imanrasekh]

ممنون از لطفتون
میشه یکم بیشتر توضیح بدین
من یکم گیج شدم

[a.r.khoshghalb]

شما می خوای ببینی کاراکتر G چند بار در زیر رشته های رشته ات اومده.
یک راه اینه که بیای همه زیر رشته ها رو پیدا کنی و ببینی تو هر کدوم چند تا G هست که خیلی کنده.
راه دیگه اینه که بیای همه G ها رو پیدا کنی و ببینی هر کدوم تو چند تا زیر رشته اومده.
مثلا در رشته :
---G----G--G-G--G
خط ها کاراکتر های دیگری هستند.
شما در این رشته در خونه های 1و6و8و11و14 کاراکتر G داری. باید هر کدوم رو ببینیم تو چند تا زیر رشته اومده.
حالا برای اینکه بفهمی خونه i اوم تو چند تا زیر رشته اومده چه کار می کنی؟
----i---------
کافیه تعداد خونه های سمت چپش رو با احتساب خود i ضرب کنی تو تعداد خونه های سمت راستش با احتساب خود i.
استدلال:
می خوای یه زیر رشته پیدا کنی که i توش باشه! پس چپ ترین خونه زیر رشته ات سمت چپ i هست با احتساب خود i و راست ترینش سمت راست i هست با احتساب خود i.
حالا میایم حالات مختلف راست ترین خونه رو در نظر میگیریم، به ازای هر حالت راست ترین خونه، به اندازه خونه های سمت چپ i حالت وجود داره (i تا)
که می شود

i * (n-i-1)

[imanrasekh]

سلام
ممنون از جوابتون
ولی زیر رشته های من مشخص هستند در برنامه بالا starta شروع زیر رشته ها رو مشخص می کنه و enda انتهای رشته ها رو مشخص می کنه
[3]starta : ابتدای رشته سوم
[3]enda : انتهای رشته سوم
ممنون میشم اگه کمکم کنید

[a.r.khoshghalb]

من راهی به ذهنم نمی رسه که توش کمتر از "تعداد حروف رشته" * "تعداد زیر رشته ها" هزینه کنیم!

[imanrasekh]

بسیار ممنون از لطفتون