C++ (יעילות)

[לושיי]

C++ (יעילות)

מישהו יכול בבקשה לקשר אותי לאתר שמסביר את נושא היעילות ב- C++ בעיקר כיצד אנו מחשבים יעילות של רקורסיה. תודה לושיי

 

[neko]

יעילות, לרבות יעילות של רקורסיה,

אינה משתנה בין שפות תכנות (לפחות לא בסדרי גודל...). ממליץ בחום על הספר ALGORITHMS של CORMEN, סביר שתוכל למצוא אותו בכל ספרייה של אוניברסיטה\מכללה. אם לא, אז חיפוש עם מילים כמו EFFICIENCY, ORDNANCE, RECURSION ודאי יניב תוצאות.

 

[Zack DA]

הערה כללית לגבי רקורסיה

כמעט ולא תמצא שימוש ברקורסיה מחוץ לספרי האלגוריתמים. רקורסיה היא בד"כ דבר לא יעיל ומסוכן מאוד מבחינת זכרון. למעט מקרים פשוטים ולינארים כמו חיפוש בינארי - רקורסיה היא לא יעילה ולא בטוחה.

 

[eyalbd]

אלא אם מדובר במבנה ש"מזמין" רקורסיה

למשל חיפוש או פעולות אחרות במערכת קבצים. כאן רקורסיה היא הפתרון המתבקש ולדעתי הפשוט והבטוח מכולם.

 

[אלדד28]

ובכלל פעולות על עצים,

ועל גרפים, ובעוד כמה וכמה תחומים שדורשים רקורסיה. צחי, אני מתפלא עליך. אתה יותר מהרבה אחרים פה אמור לדעת שהאלגוריתמים לעיתים רחוקות שוכבים בספרים ומעלים אבק.

 

[Zack DA]

להפך.... לא צריך להגזים ../images/Emo13.gif

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

 

[לושיי]

שאלה נוספת לגבי סיבוכיות

אני צריך להגיע לסיבוכיות לינארית

O​

עכשיו הגעתי לסיבוכיות כזו שאני רץ על הרשימה הראשונה ועבור כל איבר ברשימה הראשונה אני מבצע חיפוש בינארי האם הוא קיים ברשימה השנייה. האם מדובר בסיבוכיות ריבועית?