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

[zahra_zapata]

یک الگوریتم با پیچیدگی زمانی Өتتا (nlogn) ارائه نمایید که عدد صحیح x و مجموعه ی s شامل n عدد صحیح را گرفته و تعیین نماید که آیا دو عنصر در s‌وجود دارد که حاصل جمع آن ها دقیقا برابر x شود ؟

[zahra_zapata]

لطفا هر کی بلده به من کمک کنه

[Amir Oveisi]

با گراف تصمیم که از روش backtracking استفاده میکنه میشه

[zahra_zapata]

میشه بیشتر کمکم کنید.ممنون میشم.

[Amir Oveisi]

اگه بتونین به کتاب ریاضیات گسسته Rosen یه نگاه بندازین اونجا هست اگه خواستین صفحشو هم میگم

[zahra_zapata]

اگه Pdf کتاب در internet هست لطف می کنین لینکش رو برام send کنین؟وممنون میشم صفحه شو بهم بگین!

[Amir Oveisi]

فکر نکنم باشه من خودم میذارم

[zahra_zapata]

ممنونم.منتظر جوابتون هستم.

[Amir Oveisi]

امیدوارم به درد بخوره

[someCoder]

یک الگوریتم با پیچیدگی زمانی Өتتا (nlogn) ارائه نمایید که عدد صحیح x و مجموعه ی s شامل n عدد صحیح را گرفته و تعیین نماید که آیا دو عنصر در s‌وجود دارد که حاصل جمع آن ها دقیقا برابر x شود ؟
یه راه ساده اینه: اول با o(nlogn) سورت کن، بعد دو تا اشاره گر به اول و آخر آرایه بگیر و برحسب اینکه مجموع دو تا عدد که اشاره گرها نشون میدن چیه، یکیشون رو بطرف داخل آرایه حرکت بده و همن کار رو ادامه بده تا پیدا کنی.
مشکل داشتی بگو

[Amir Oveisi]

البته باید sort شده باشن عددها بقیه باید طبق روش backtracking باشه تا این پیچیدگی زمانی رو داشته باشه:متفکر:

[zahra_zapata]

امیدوارم به درد بخوره
ازبابت راهنماییتون ممنونم.
موفق باشید


یه راه ساده اینه: اول با o(nlogn) سورت کن، بعد دو تا اشاره گر به اول و آخر آرایه بگیر و برحسب اینکه مجموع دو تا عدد که اشاره گرها نشون میدن چیه، یکیشون رو بطرف داخل آرایه حرکت بده و همن کار رو ادامه بده تا پیدا کنی.
مشکل داشتی بگو
از بابت راهنماییتون ممنون.

[someCoder]

قابلی نداشت!

[Amir Oveisi]

خواهش میکنم