خب چه الگوریتمی حریصانه است؟ الگوریتمی که تو هر مرحله دنبال بهترین راه حل مبتنی بر صرفا همون اطلاعات اون لحظه است. به طبع منظورمون بهترین راه در راستای رسیدن به خواسته مسئله است.
مثال؟ بله. شما میخوای تو یه کتاب فروشی که nتا کتاب داره، با یه بودجه مشخص r ریالی کتاب بخری. میدونی قیمت کتاب iام هم برابره با c_i. خب یه راهکار حریصانه اینجا چه معنیای میده؟ اول دنبال ارزونترین کتاب بگردی. بعد از بین مابقی دوباره دنبال ارزونترین کتاب بگردی و اونقدر ادامه بدی که بودجهات کفاف خرید کتاب بعدی رو نده. اینجا تو هر مرحله که یه تعداد مشخصی کتاب باقی مونده بودن، دنبال بهترین راه یعنی انتخاب ارزونترین موجودی گشتیم.
به طور خلاصه پیدا کردن یه روش حریصانه و محاسبه پیچیدگی زمانیش ساده است و در مقابل اثبات درستیش دشوار.