יעילות - אני צריך ללמוד את כל הנושא הזה... עריכה: או שלא?

[SweeT_EviL]

יש למישהו איזשהוא משהו שיכול לעזור לי? זה לא אמור לשנות לאיזה שפה זה אבל למתעניינים C+ASM+JAVA ואולי עוד..

דרך אגב קראתי איזה 3 דפים שונים בויקיפדיה, עזר מעט - בלבל הרבה.

עריכה:

מצאתי איזה ספר בבית, אני מניח שהבנתי =\

[SweeT_EviL]

במקום לפתוח חדש, אני מקפיץ את זה.

רציתי לדעת אם זמן הריצה הוא O(2n log n)

התוכנית:

void sort(int a[],int size)
{
	int arr1[4];
	int arr2[4];
	int i, arr2s;

	if(size<=1)
		return;

	for(i=0;i<size;i++)
	{	
		if(size/2>i)
			arr1[i]=a[i];
		else
			arr2[i-(size/2)]=a[i];
	}

	arr2s = size%2==0 ? size/2 : (size/2)+1;

	sort(arr1,size/2);
	sort(arr2,arr2s);

	combine(a, arr1, arr2, size, size/2, arr2s);
}

void combine(int a[], int arr1[], int arr2[], int size, int sArr1, int sArr2)
{
	if(size==0)
   	return;
	if(sArr2==0 || arr1[0] < arr2[0] && sArr1>0)
	{
		a[0]=arr1[0];
		combine(a+1, arr1+1,arr2, size-1, sArr1-1, sArr2);
		return;
	}
	a[0]=arr2[0];
	combine(a+1, arr1,arr2+1, size-1, sArr1, sArr2-1);
}

דרך אגב, יש איך לשפר את מה שעשיתי? (במקום COMBINE אני יכול לשים FOR אבל שיהיה..)

[Ghosthunter]

combine - o(n)

sort -

t(n)=2t(n/2)+n+combine

t(n)=2t(n/2)+2n

לפי שיטת האב -

t(n)=teta(nlogn)

[SweeT_EviL]

אני מניח שלא הכי הבנתי את נושא היעילות..

אני מניח שT מסמל פונקציה כמו כל דבר (F)(...)

אבל מה זה TETA, ואיך הגעת מ-nlogn ל2t(n/2)...

עריכה:

ולמה אני, או יותר נכון איך אני עושה שהמערכים יהיו גמישים - בסגנון הזה:

int arr1[size/2];

int arr2[size/2 + 1];

[ktbnus]

הקצאה דינמית

[lo_toda]

הוא ניסה להסביר לך שזה קרוב לל NLOGN ולא ל N^2

שזה יותר מהיר ...לא הכי מהיר ....אני ראתי יותר מהירים ...

[SweeT_EviL]

אני יודע שזה יותר מהיר מN^2 אחרי הכל אני עשיתי את זה

אז הסופי הוא NLOGN?

אבל אם יש שני N, כל אחד לחוד זה לא יוצר 2N?

ומכאן הגעתי ל2NLOGN

פשוט לא מבין את הפונקציה שלו, דרך אגב מה עם השאלה השניה?

[Ghosthunter]

אני מניח שלא הכי הבנתי את נושא היעילות..

אני מניח שT מסמל פונקציה כמו כל דבר (F)(...)

אבל מה זה TETA, ואיך הגעת מ-nlogn ל2t(n/2)...

עריכה:

ולמה אני, או יותר נכון איך אני עושה שהמערכים יהיו גמישים - בסגנון הזה:

int arr1[size/2];

int arr2[size/2 + 1];

T זו פונ זמן הריצה של התוכנית. הגעתי ממנה לזמן הריצה ע"י שיטת האב(חיפוש קצר בגוגל וכניסה לויקיפדיה יתן לך מידע. אם יהיו לך עוד שאלות, תוכל לשאול).

זמן הריצה של מיון בשיטה MERGE SORT דומה לזמן הריצה של QUICK SORT. זמן הריצה של שניהם הוא nlogn, והוא זמן הריצה הקצר ביותר לפונקציות מיון(מהסוג הזה, בו לא ידוע תחום הקלט מראש).

טטה זו אות יוונית(כמו O-אוקימורון). האות מציינת חסם אסימפטוטי משני הכיוונים(גם Oמלמעלה, וגם אומגה מלמטה).

אם אתה לומד זמן ריצה בתיכון, בו מלמדים או Oבלבד, אתה יכול להגיד שזמן הריצה הוא o(nlogn) (כזכור טטה זה גם O וגם אומגה).

ד.א

 o(g(n))=o(f(g(n)))

כאשר f(n) היא פונקציה ליניארית.

[SweeT_EviL]

לא למדתי בתיכון על יעילות, מצאתי איזה ספר בבית שיש קצת על החומר הזה אז ממנו קראתי, בנוסף לחומר שבויקיפדיה. רק אותו קראתי ראשון אז זה די בילבל אותי ולא תרחתי לקרוא אותו שוב לאחר שקראתי בספר ההוא.

[Electric Boom]

אני יודע שזה יותר מהיר מN^2 אחרי הכל אני עשיתי את זה

אז הסופי הוא NLOGN?

אבל אם יש שני N, כל אחד לחוד זה לא יוצר 2N?

ומכאן הגעתי ל2NLOGN

פשוט לא מבין את הפונקציה שלו, דרך אגב מה עם השאלה השניה?

הבדל של קבוע

כשמתעסקים ביעילות מדובר במונחים אסימפטוטיים, ההכפלה\הוספה בקבוע 'לא משפיעה', יענטו עדיין אותה "משפחת" זמן ריצה

[Ghosthunter]

הנה עוד הסבר קצר שרשמתי מהר(תשנו את הסיומת לDOC. משום מה הוא לא נותן להעלות קבצים כאלו):

[attachment deleted by admin]

[lo_toda]

שכח מזה בנתיים ....באוניברסיטה זה נקרא ממבני נתונים ....

[Electric Boom]

תלוי

לנו יש (יהיה השנה) קורס ביעילות..

[Ghosthunter]

יש לכם קורס בסיבוכיות וחישוביות. זה לא קשור לחומר הזה.

[Electric Boom]

אז?