当面对求解一个问题的新算法的时候,我们的兴趣在于形成这样一种粗略的认识:新算法预期能有多好,对于同一个问题它比其他的算法如何。计算复杂性研究能够提供这种认识。对算法的分析能够帮助我们对算法更深入地理解,并能够提出有根有据的改进。尤为重要的是,正确分析所需要的仔细全面的审查常常使得算法更好和更有效地实现。激励学习因为具有较强的在线自适应性以及对复杂系统的自学习能力,受到机器人导航研究者的关注。目前,激励学习对于许多现实的问题,如大尺度和部分可观测环境,仍然是没有解决的问题。这些问题采用传统的算法很难满意地解决。通过利用人工势场将激励学习问题转换为路劲规划问题。然后为解决人工势场中的局部最小问题,应用虚拟水流法的概念提出的一种新的人工势场算法。实验结果表明该方法在激励学习系统中是有效的。但只有当解析的结果与经验研究一致的时候,我们才会确信算法的合理性以及分析过程的正确性。为了说明该方法的合理性和正确性,本论文将从解析的结果与经验研究两方面对此算法进行了分析和研究。主要工作陈述如下:(1)对算法复杂性分析的方法、涉及的数学知识、研究现状和现实意义进行了综述性介绍。(2)研究了人工势场中斥力势函数和引力势函数的选取,重点研究了如何将激励学习模型转换成人工势场模型。(3)用网格世界问题对激励势场模型进行了测试。实验结果表明:该算法能简洁有效地给出理想的解。(4)给出了虚拟水流算法的数学模型,分析在最坏的情况下,其算法时间复杂度为O((n(n-1))/2)同时求出了算法的空间复杂度。