الگوريتم ديکدينگ کروي به عنوان الگوريتمي نزديک به بهينه براي حل مساله کمترين مربعات در بسياري از کاربردهاي مخابراتي مورد توجه است. از ويژگيهاي اين الگوريتم کارايي مطلوب و پيچيدگي معقول آن ميباشد. روشهاي موجود براي پيادهسازي الگوريتم ديکدينگ کروي معمولا به حل مساله در فضاي حقيقي ميپردازند در حالي که در بسياري از کاربردهاي مخابراتي پارامترهاي سيستم مقادير مختلط هستند. براي حل مساله ديکدينگ کروي با پارامترهاي مختلط در فضاي حقيقي به ناچار بايد معادله سيستم به معادلهاي در فضاي حقيقي تبديل شود. با اين کار ابعاد فضاي جستجو دو برابر ميشود و به طبع آن پيچيدگي و زمان همگرايي آن افزايش مي يابد. اخيرا روشهايي براي حل مساله ديکدينگ کروي در فضاي مختلط ارائه شده است. در اين مقاله به بررسي پيچيدگي اين روشها ميپردازيم و يک حد تئوری برای محاسبه پیچیدگی آنها ارائه میدهیم
