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

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


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

الگوریتم با (O(n برای یافتن دو عنصر با مجموع X در یک آرایه مرتب

+2 امتیاز
252 بازدید
سلام

اگر S یک مجموعه از اعداد حقیقی باشد و یک عدد حقیقی x داشته باشیم که

به دنبال 2 عدد از این مجموعه هستیم که جمع آنها دقیقا برابر x باشه

اگر فرض کنیم که آرایه از قبل مرتب هست الگوریتمی با زمان n ارائه دهید

( تمرین 4-8 کتاب Steven Skiena )
سوال شده دی 14, 1393  بوسیله ی Pakniat (امتیاز 382)   2 5 27
البته این سوال  یک حالت خاص برای یکی از مسایل NP_Complete یعنی Subset sum problem هستش. در sub set problem فقط مهم هست که یکسری عدد پیدا کنیم که جمع دقیقا x بشه . خیلی جالبه که یک تغییر به این سادگی  میتونه یک مساله از مرتبه n رو به یک مساله غیر قابل حل تبدیل کنه :)

1 پاسخ

+2 امتیاز
 
بهترین پاسخ

کد ++C :

std::pair<int, int> find_equal_sum(const std::vector<int>& arr,const int x)
{
    int max = arr[arr.size()-1];//O(1)
	//std::vector<int> direct_index_hash(max+1, 0);//O(n)
	std::vector<int> direct_index_hash(max+1, 0);//O(k)
	for (size_t i = 0; i < arr.size(); i++)//O(n)
		direct_index_hash[arr[i]] ++;
	for (size_t i = 0; i < arr.size(); i++)//O(n)
	{
		int diff = x - arr[i];
		if (diff <0) 
			continue;
		int diff_count = direct_index_hash[diff];
		if (diff == arr[i]){
			diff_count--;
		}
		if (diff_count >0)
			return std::make_pair(arr[i], diff);
	}
	return std::make_pair(-1, -1);//agar 2 onsoor ba majmoo x vojood nadasht
}

اجرای کد 

توضیح الگوریتم :

ورودی :

  • arr : آرایه  مرتب
  • X : جمع 2 عنصر از آرایه باید این عدد شود.

خروجی :

  • pair(a,b : دو عنصری که جمعشان X هست .

 

  1.  متغیر i را 0 می گذاریم
  2.  تفاضل عدد x با عنصر i ام arr را حساب می کنیم diff=x-arr[i
  3. مقدار diff رو درآرایه مرتب arr  جست و جو می کنیم اگر موجود بود یعنی [arr[i و diff  دو عنصر مورد نظر هستند .
  4. i را یک واحد اضافه می کنیم مرحله 2 را تا رسیدن به  انتهای آرایه یا جواب تکرار می کنیم.

 

چون قسمت 2 الگوریتم در بدترین حالت n بار تکرار میشه جست و جو باید در (1)O انجام بشه تا پیچیدگی کلی n بشه پس تنها راهی که وجود داره استفاده از hash table از نوع direct addressing هست (وکتور direct_index_hash داخل کد بالا)

میشه گفت این الگوریتم  تقریبا مشابه counting sort هست .

ویرایش:

البته پیچیدگی الگوریتم بالا (O(n+k هست که k طول بزرگترین عدد آرایست (من ساختن وکتور در خط دوم رو (O(n گرفته بودم که درست نیست ).چون سوال حرفی درباره k نزده k خودش میتونه با سرعتی بیشتر از n مثلا n^2 رشد داشته باشه پس  نمیشه گفت الگوریتم بالا در بدترین حالت (O(n هست(فقط در صورتی (O(n هست  که بازه اعداد حقیقی ورودی تابع محدود باشه) 

اگر آرایه sort شده میشه از این روش با (O(n استفاده کرد :

#include <algorithm>
#include <iostream>
#include <vector>

std::pair<int, int> find_equal_sum(const std::vector<int>& arr, const int x)
{
	if (arr.size()>1){
		int first = 0;
		int last = arr.size() - 1;
		while (first < last){//O(n)
			if (arr[first] + arr[last]>x)
				--last;
			else if (arr[first] + arr[last]<x)
				++first;
			else if (arr[first] + arr[last] == x){
				return std::make_pair(arr[first], arr[last]);
				break;
			}
		}
	}
	return std::make_pair(-1, -1);
}
int main()
{
	const int x = 19;
	std::vector<int> arr{ 5, 7, 8, 11, 12 };
	auto res = find_equal_sum(arr, x);
	std::cout << res.first << " " << res.second;
	return 0;
}

 

پاسخ داده شده دی 15, 1393 بوسیله ی BlueBlade (امتیاز 15,742)   13 17 85

آره ا worst case میشه k .

best case میشه n (حالتی که k از n سرعت رشد کمتری داره)

,ولی میانگین هم  k میشه چون باید از همه حالت هایی که هم k و هم  n میتونن داشته باشن میانگین بگیریم ! که همچین چیزی میشه :( این میانگین پیچیدگی ساختن وکتور کد بالا هست. همین طور که مشخصه چند جمله ای هم نیست و بر حسب تعداد ارقام به شکل نمایی رشد می کنه ! پس طبیعتا سرعت رشد ساخت وکتور از میانگین جست و جو که n هست بیشتر هستش.)

 

ممنون
پس الگوریتم نمایی هست ,
با جستجوی دودویی حداقل nlgn هست که اما چجوری میشه با n پیاده سازی کرد
پیاده سازی با (O(n رو با فرضی که کتاب کرده (مرتب بودن آرایه ) داخل کد بالا گذاشتم . بعید میدونم در صورت مرتب نبودن راهی با پیچیدگی کمتر از nlogn وجود داشته باشه (احتمالا  قابل اثبات هم هست ( با روشی مثل اثبات upper bound  ا nlong الگوریتم های sort با مقایسه ))
...