imanrasekh
دوشنبه 30 تیر 1393, 10:56 صبح
سلام
من یک برنامه خیلی ساده دارم که مرتبه اجراییش 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;
}
من یک برنامه خیلی ساده دارم که مرتبه اجراییش 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;
}