الگوریتم با پیچیدگی زمانی کمتر برای بدست آوردن عنصر n ام در آرایه شامل ضرب عناصر خودش در هم - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۵۹ نفر آنلاین
۰ عضو و ۱۵۹ مهمان در سایت حاضرند

الگوریتم با پیچیدگی زمانی کمتر برای بدست آوردن عنصر n ام در آرایه شامل ضرب عناصر خودش در هم

0 امتیاز
100 بازدید

من یک آرایه n عنصری دارم میخواهم عنصر n ام در آرایه ای که شامل ضرب عناصر این آرایه در هم باشه رو پیدا کنم .

این الگوریتم فعلی هستش :

vector<int> arr={....};
vector<int> temp;

//O(n^2)
for(int i=0;i<arr.size();i++)
   for(int j=0;j<arr.size();j++)
       temp.push_back(arr[i]*arr[j]);

sort(temp.begin(),temp.end());//O(nlogn)
return temp[n];//O(1)

که (O(n^2 هستش آیا راهی بهتر با  پیچیدگی زمانی کمتر وجود داره ؟

سوال شده دی 30, 1393  بوسیله ی َAI (امتیاز 304)   1 4 26

1 پاسخ

+1 امتیاز
سلام

در کد n*n بار ضرب انجام میشه که تقریبا نصف اونها تکراری هست میشه با dynamic programming تعداد ضرب های تکراری رو کم کرد اما پیچیدگی همون n^2 هست

اگر اصرار دارید تمام عناصر دو به دو در هم ضرب بشند پیچیدگی همون n^2 هست اما اگر ضرب عناصر آرایه در درایه n ام باشد پیچیدگی n هست ،

اگر میشه یک مقدار در مورد هدف تون از این الگوریتم بیشتر توضیح بدید
پاسخ داده شده بهمن 3, 1393 بوسیله ی Pakniat (امتیاز 382)   2 5 27
...