تکنیک گریدی

[sarakh]

سلام کسی می دونه پیچیدگی زمانی و فضایی تکنیک گریدی چقدره؟همراه با دلیل؟ممنون.

[sarakh]

یعنی کسی نمی دونه؟؟؟؟؟؟؟؟؟؟؟؟؟

[javanerd]

یعنی کسی نمی دونه؟؟؟؟؟؟؟؟؟؟؟؟؟
برای حل کردن چه مساله‌ای؟؟؟!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!

[sarakh]

مسئله خاصی مد نظر نیست.مثلا برای جستجوی اول سطح پیچیدگی فضایی و زمانی (b^d)
O

[Pooria121]

Greedy یک تکنیک یا به عبارت دیگر یک فلسفه برای پیدا کردن Optimal Solution برای یک مسئله است، و همیشه همان جواب optimal نیست
مثلا Algorithm هایی زیر Greedy هستند ولی Time Complexity هاشون باهم متفاوت هست.

Dijkstra's Algorithm: O(|E| log |V|) (E baraye Edges hast V vase Vertexes dar dakhele ye Graph) baraye pedya karde single-source shortest path
Union : O(n log n)^2 - hamoon tor ke mibinid inja Exponential hast
Quick Union: O(n + m log n)

Kruskal's Algorithm: O(|E| log |E|) baraye peyda kardane minimum spanning tree dar ye graph

Prime's Algorithm: O(|E| log |V|)



و همانطوری که در بالا میبیتند مثال های متفاوت پیچیدگی های متفاوتی دارند و اگر به آدرس زیر مراجعه کنید : http://en.wikipedia.org/wiki/Algorithm#By_complexity
متذکر این موضوع شده که تکنیک هارو کلاس بندی بر مبانی complexity ، درست نیست کرد، ولی خوب شما بعضی موقع های میتوانید در بعضی از موارد اثبات کنید که به عنوان مثال برای search یا sort می نمیتوانیم کمتر از O(n) یا O(nlog n) داشته باشیم ...