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

[parisa.porseshgar]

سلام به همه حاضرین

قبل از طرح سوالم خیلی کوتاه می خوام از جناب آقای فرهاد شیری تشکرررررررر کنم که پاسخ من رو توی سوال قبلیم دادن.
ممنونممممممم ازشون واقعا که باعث شدن مسئله برام دیگه فهمیدنی شده حالااااااا.

مسئله ای رو باهاش رو به رو شدم این طور ازم خواسته که یک آرایه ی n عصنری ( اسمش a )، که تشکیل شده از اعداد صحیح مثبت و یک متغییری داریم اسمش k هست حالا می خوایم یه طوری این دوتا عدد رو توی آرایه a موجودمون پیدا کنیم که مجموعشون بشه همون K خودمون.
یه الگوریتمی باید طراحی بشه براش با پیچیدگی زمانی O(n) که جای این دوتا عدد ( اگر وجود دارن ) رو چاپ کنه.

یعنی مثلا
a=[6,3,2,1,8] که خوب n میشه مسلما 5 و k میشه 8 و اون دوتا عددمونم میشن 6 و 2

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

[farhad_shiri_ex]

قبل از طرح سوالم خیلی کوتاه می خوام از جناب آقای فرهاد شیری تشکرررررررر کنم که پاسخ من رو توی سوال قبلیم دادن.
ممنونممممممم ازشون واقعا که باعث شدن مسئله برام دیگه فهمیدنی شده حالااااااا.

تشکر از لطف شما.!

کسی هست که بتونه بهم کمک کنه برام توضیح بده تا من بتونم یادش بگیرم...

البته کسی هست! این جمله خیلی مناسب برای پرسیدن سوال در انجمن نیست!! به این علت که قطعا خیلی از دوستان این انجمن هستند که به راحتی می توانند این الگوریتم ها را بنویسن!

در جواب سوالتون هم میشه یک همچنین الگوریتمی نوشت که تقریبا زمان محاسبه (O(n باشه یا به تعبیری ورودی الگوریتم متناسب با الگوریتم به صورت خطی رشد خواهد کرد...

n = 5 , k =8 

n - 1   = 4

n - 2   = 3

n - 3   = 2 

n - 4   = 1

4+3+2+1 = 10

O(n(n/2))

و اینهم یک برنامه کوچک ...

#include <iostream>



using namespace std;



int main()

{



    int n=5 ,k=8 ;

    //int A[] = {6,3,2,1,8};

    int A[] = {1,2,3,6,8}; // sorted array



    for(int i =0; i < n; i++){

       for(int j = i + 1; j < n ; j++)

           if((*(A + i) + *(A + j)) == k)

            cout << *(A + i) << " + " << *(A + j) << " = " << k << '\n';

    }



    return 0;

}

[parisa.porseshgar]

سپاس گزارم از شما استاد.