بهترین الگوریتم با پیچیدگی زمان مناسب

[alborzi_66]

ما n تا عدد داریم و می خواهیم الگوریتمی را ارائه دهیم که پیچیدگی زمان آن o=(n^2) باشد بطوریکه این الگوریتم دو عدد را از این n عدد را بیابد که جمع آنها مساوی عدد ثابت k شود.

بهترین الگوریتم با پیچیدگی زمان مناسب

[amirniknam]

اين الگوريتم رو ميشه با مرتبه زماني n log n نيز حل كرد (كمتر از n^2)
ابتدا ليست رو با مرتبه زماني n log n مرتب ميكنيم (مثلا با mergsort)
بعد يك اشاره گر در ابتداي ليست و يك اشاره گر در انتهاي ليست قرار ميدهيم سپس عدد ابتدا و انتهاي ليست را با هم جمع ميكنيم اگر از عدد مورد نظر كوچكتر بود اشاره گر ابتداي ليست را يك خانه جلو مي بريم و اگر از عدد مورد نظر بزرگتر بود اشاره گر انتهاي ليست را يك خانه عقب مي آوريم تا به عدد مورد نطر برسيم يا اينكه اشاره گرها به هم برسند

[alborzi_66]

اين الگوريتم رو ميشه با مرتبه زماني n log n نيز حل كرد (كمتر از n^2)
ابتدا ليست رو با مرتبه زماني n log n مرتب ميكنيم (مثلا با mergsort)
بعد يك اشاره گر در ابتداي ليست و يك اشاره گر در انتهاي ليست قرار ميدهيم سپس عدد ابتدا و انتهاي ليست را با هم جمع ميكنيم اگر از عدد مورد نظر كوچكتر بود اشاره گر ابتداي ليست را يك خانه جلو مي بريم و اگر از عدد مورد نظر بزرگتر بود اشاره گر انتهاي ليست را يك خانه عقب مي آوريم تا به عدد مورد نطر برسيم يا اينكه اشاره گرها به هم برسند

میشه کد اون رو یا شبه کدشو واسم در بیارین( اخه واسم مهمه)
ممنون

[pesar irooni]

سلام دوست عزیز
اینم کدش با زمانی که دوستمون به درستی گفت n log n


SUM-X(S, x)
MERGE − SORT(S)
i=1
j= n
while i < j
do if S[i] + S[j] < x
then i i + 1
else if S[i] + S[j] > x
then j j − 1
else return S[i], S[j]
if i = j
then return nil

[pesar irooni]

این چیز که نوشتم شبه کده. به زبان خاصی نیست. کاملا هم واضحه. باز اگه نیاز داشتید بگید به کدوم زبون مسلطید که کدش رو به اون زبون بنویسم.

[alborzi_66]

به همون زبون c+ خوبه اما اگه ميشه كد كاملشو كه اجرايي باشه بنويسين البته اگه زحمتي نيست

[pesar irooni]

چشم
براتون مینویسم تا فردا

[mortezamsp]

با عرض سلام.آقا ببینید اینی که من نوشتم درسته؟ کد سی پلاس هست.


void buble_sort(int *aray , int lenth)
{
...
}

void find(int *aray ,int lenth ,int k , int *x1 , int *x2)
{
int i=0;
int j=lenth;
while(i!=j)
{
if( aray[i]+aray[j] > k )
j--;
else if( aray[i]+aray[j] < k )
i++;
else if( aray[i]+aray[j] == k )
{
x1=aray[i];
x2=aray[j];
break;
}//end of if
}//end of while

}

void main()
{
int aray[lenth]=...//aray
int lenth;
buble_sort(aray , lenth);
int k=...
int x1;
int x2;
find(aray , lenth , k , *x1 , *x2);
cout<<k<<"="<<x1<<"+"<<x2;
getch();
}

[pesar irooni]

اینم کدش به زبون ++C

#include "stdio.h"

//*****MERGE SORT********************************************** *
const int MAX_SIZE = 50;
void Merge(int A[], int F, int Mid, int L)
// ---------------------------------------------------------
// Merges two sorted array segments A[F..Mid] and
// A[Mid+1..L] into one sorted array.
// Precondition: F <= Mid <= L. The subarrays A[F..Mid] and
// A[Mid+1..L] are each sorted in increasing order.
// Postcondition: A[F..L] is sorted.
// Implementation note: This function merges the two
// subarrays into a temporary array and copies the result
// into the original array A.
// ---------------------------------------------------------
{
int TempArray[MAX_SIZE]; // temporary array
// initialize the local indexes to indicate the subarrays
int First1 = F; // beginning of first subarray
int Last1 = Mid; // end of first subarray
int First2 = Mid + 1; // beginning of second subarray
int Last2 = L; // end of second subarray
// while both subarrays are not empty, copy the
// smaller item into the temporary array
int Index = First1; // next available location in
// TempArray
for (; (First1 <= Last1) && (First2 <= Last2); ++Index)
{ // Invariant: TempArray[First1..Index-1] is in order
if (A[First1] < A[First2])
{ TempArray[Index] = A[First1];
++First1;
}
else
{ TempArray[Index] = A[First2];
++First2;
} // end if
} // end for
// finish off the nonempty subarray
// finish off the first subarray, if necessary
for (; First1 <= Last1; ++First1, ++Index)
// Invariant: TempArray[First1..Index-1] is in order
TempArray[Index] = A[First1];
// finish off the second subarray, if necessary
for (; First2 <= Last2; ++First2, ++Index)
// Invariant: TempArray[First1..Index-1] is in order
TempArray[Index] = A[First2];
// copy the result back into the original array
for (Index = F; Index <= L; ++Index)
A[Index] = TempArray[Index];
} // end Merge
void Mergesort(int A[], int F, int L)
// ---------------------------------------------------------
// Sorts the items in an array into ascending order.
// Precondition: A[F..L] is an array.
// Postcondition: A[F..L] is sorted in ascending order.
// Calls: Merge.
// ---------------------------------------------------------
{
if (F < L)
{ // sort each half
int Mid = (F + L)/2; // index of midpoint
Mergesort(A, F, Mid); // sort left half A[F..Mid]
Mergesort(A, Mid+1, L); // sort right half A[Mid+1..L]
// merge the two halves
Merge(A, F, Mid, L);
} // end if
} // end Mergesort
//*****END OF MERGE SORT****************************************
//*****FIND SUM-X***********************************************
void SUMX(int S[],int n, int x)
{
Mergesort(S,0,n-1);
int i=0,j=n-1;
while (i < j)
{
if (S[i] + S[j] < x)
i=i + 1;
else if (S[i] + S[j] > x)
j=j - 1;
else
{
printf("\nThe sum of %d and %d in this array is %d",S[i],S[j],x);
return;
}
}
if (i == j)
{
printf("\nThis array have not any two numbers that their sum be %d ",x);
return;
}
}
//*****END OF SUM-X************************************************* *****
void main()
{
//example
int a[]={2,20,10,5,46,11,81};
SUMX(a,7,91);
}

[pesar irooni]

:اشتباه:آقای مرتضی رو چه حساب از buble sort استفاده کردید. بدترین الگوریتم مرتب سازی که میتونستید انتخاب کنید و زمان ما رو به (n^2) افزایش میده.

[pesar irooni]

آقای / خانم mortezamsp رو چه حساب از bubble استفاده کردید.:اشتباه: بدترین الگوریتم مرتب سازی که میشه انتخاب کرد و زمان الگوریتم ما رو به n^2 افزایش میده.