بابک

بابک

بابک

بابک

بابک

این جا برای این است که هر از چندی دلنوشته و یا خواسته ای را بنویسم. البته خالی از مطالب علمی هم نخواهد بود.

طبقه بندی موضوعی

الگوریتم غربال اراتستن

پنجشنبه, ۱۰ فروردين ۱۳۹۱، ۱۰:۴۲ ب.ظ

الگوریتم غربال اراتستن ( seive of erathosten )  یکی از معروفترین الگوریتم های معروف برای پیدا کردن اعداد اول هست که پیچیدگی زمانی آن ( O( nlglg n  می باشد . 

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

ابتدا الگوریتم غربال ارتستن را توضیح داده سپس سراغ الگوریتم بهبود یافته خواهیم رفت . 

الگوریتم غربال اراتستن : از عدد 2 شروع کرده ، تمام ضرایب آن که عددی مرکب خواهد بود را حذف می کنیم ، سپس سراغ اولین عدد حذف نشده ی بعدی می رویم ( که این عدد هم طبیعتا اول هست ) و این کار را ادامه می دهیم . 

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

// cpp code

#include <iostream>
using namespace std;

const int maxn=1000*1000;

bool v[maxn]={true,true};
#define FOR(i,t,n) for((i)=(t);(i)<(n);(i)++)

void sieve(int n){
	int i,j;
	FOR(i,2,n)if(!v[i])
		for(j=i+i;j<n;j+=i)
			v[j]=true;
}

کد یه کم بهتر :

// cpp code a bit better

#include <iostream>
using namespace std;

const int maxn=1000*1000;
bool v[maxn]={true,true};

void sieve(int n){
	int i,j;
	for(i=2;i*i<n;i++)if(!v[i])
		for(j=i*i;j<n;j+=i)
			v[j]=true;
}

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes


خوب میریم سراغ الگوریتم با پیچیدگی خطی : 


این کار را با استفاده از اصل اکسترمال انجام می دهیم . به ازای هر عدد کوچکترین عامل اول آن را بدست می آوریم . که آن را در آرایه ی lp ذخیره می کنیم . و  همین طور  باید آرایه ای داشته باشیم که اعداد اول را در آن  مشخص کنیم که آن را pr  می نامیم . 

به ازای هر عدد i بین 2  و n دو حالت داریم :

1 - lp[i]==0  ، که یعنی این که هنوز کوچکترین عامل اول این عدد پیدا نشده است ، پس کوچکترین عامل اول آن خودش خواهد بود

2 - lp[i]!=0 ، که یعنی این که کوچکترین عامل اول این عدد مشخص شده است . 

برای هر دو حالت ، تمام اعداد اول کوچکتر از این عدد را در نظر میگیریم ، و تا زمانی که از کوچکترین عامل اول این عدد ، کوچکتر هست ، ضرایب آن را حذف می کنیم . 


پیاده سازی الگوریتم : 

// cpp code

#include <iostream>
using namespace std;

const int maxn=1000*1000;

int lp[maxn],pr[maxn];
int size; // size of prime numbers 


void sieve_new(int n){
  int i,j;
	for (i=2; i<n; ++i) {
		if (lp[i] == 0) {
			lp[i] = i;
			pr[size++]=i;
		}
		for (j=0; j<size && pr[j]<=lp[i] && i*pr[j]<n; ++j)
			lp[i * pr[j]] = pr[j];
	}
}


اثبات صحیح بودن الگوریتم و اثبات خطی بودن الگوریتم :


نکته ی ساده و جالبی که وجود دارد این است که هر عدد را می توان به صورت i= lp[i]*x  نوشت که عملا این عدد حتما چک شده است و نکته ی جالبتری که وجود دارد این است که هر i فقط یک بار چک می شود  علت آن هم این است که می دانیم فرض کنید برای یک عدد خاص مانند n ، دو عدد مانند i و j وجود دارند که n  برابر i*p  و j*q  شده است که در این صورت یعنی کوچکترین عامل n هم p هست و هم q که در این صورت یعنی p=q  و مشخصا i =j خواهد بود . 


توانستیم الگوریتمی خطی ارایه بدهیم ، ولی عملا خود الگوریتم غربال ، با الگوریتم خطی خیلی فرقی نمی کند :)

ولی خوب نکته ای که هست این است که حداقل یه تغییر مثبت داشته ایم و از همه مهم تر این ایده ی کوچکترین مقسوم علیه می باشد که بسیار ایده ی پر کاربردی هست . 

( برای این که جالب بودن این ایده را ببینید می تونید این سوال را با پیچیدگی زمانی خطی حل کنید )


با تشکر

عید نوروز 1391 ( باورم نمیشه :) . تو عید حوصله ام شد اینو بنویسم ، له لهم ، داغونماااا.... )


موافقین ۲ مخالفین ۰ ۹۱/۰۱/۱۰
بابک احمدی

نظرات  (۴)

 خیلی خوب بود! :)
Agha babak mamnun kheeeeeeeeili useful!! :D
چرا تو وب من نمیاد؟
۲۰ آذر ۹۴ ، ۲۳:۴۷ ابتین باطنی
خیلی خوب بود فقط لطفا منبعش رو هم بگید
پاسخ:
اون موقعی که اینو نوشتم، یه سوال از codechef حل کرده بودم که باید با پیچیدگی زمانی خطی حل میشد، الان سوالش یادم نیست

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی