אלגוריתם עטיפת המתנה

מתוך המכלול, האנציקלופדיה היהודית
(הופנה מהדף הצעדה של ג'ארביס)
קפיצה לניווט קפיצה לחיפוש
Crystal Clear app help index.svg
ערך מחפש מקורות
רובו של ערך זה אינו כולל מקורות או הערות שוליים, וככל הנראה, הקיימים אינם מספקים.

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

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

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

הצגה גרפית של האלגוריתם

צעדת ג'רוויס או אלגוריתם עטיפת המתנה הוא אלגוריתם למציאת הקמור של נקודות במישור.

האלגוריתם נקרא על שם ריי ג'רוויס שפרסם את האלגוריתם בשנת 1973, אף על פי שהאלגוריתם התגלה במקביל בתקופה זו על ידי מספר חוקרים.

סיבוכיות זמן הריצה של האלגוריתם היא (O(nh כאשר n הוא מספר הנקודות הכולל ו-h הוא מספר הנקודות שירכיבו את הקמור בסופו של דבר.

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

ניתן להשתמש באלגוריתם גם עבור מספר רב של ממדים.

P Computer-science.svg ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום למכלול ולהרחיב אותו.
Logo hamichlol 3.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0