java – 数独求解器的算法复杂度(Big-O)
|
我正在寻找“你如何找到它”,因为我不知道如何找到我的程序的算法复杂性.
我用java编写了一个数独求解器,没有效率(我想尝试让它递归工作,我成功了！) 一些背景： 我的策略采用回溯来确定,对于给定的数独谜题,谜题是否只有一个独特的解决方案.所以我基本上阅读了一个给定的谜题并解决它.一旦我找到了一个解决方案,我不一定完成,需要继续探索进一步的解决方案.最后,三种可能的结果之一发生：难题根本无法解决,拼图有独特的解决方案,或者拼图有多种解决方案. 我的程序从一个文件中读取拼图坐标,该文件对于每个给定的数字有一行,包括行,列和数字.根据我自己的惯例,7的左上角正方形写为007. 执行： 我从文件中加载值,并将它们存储在二维数组中 我的程序如何算法复杂度？我认为它可能是线性的[O(n)],但我多次访问该数组,所以我不确定:( 任何帮助表示赞赏 解决方法
O(n ^ m)其中n是每个方格的可能性数(即经典数独中的9),m是空白的空格数.
这可以通过仅从一个空白向后工作来看出.如果只有一个空白,那么你有可能在最坏的情况下必须完成.如果有两个空白,则必须为第一个空白处理n种可能性,对于第一个空白的每种可能性,必须为第二个空白处理n种可能性.如果有三个空白,那么你必须为第一个空白处理n种可能性.这些可能性中的每一种都将产生具有两个空白的拼图,其具有n ^ 2种可能性. 该算法通过可能的解决方案执行深度优先搜索.图表的每个级别代表单个正方形的选择.图表的深度是需要填充的正方形的数量.在分支因子为n且深度为m的情况下,在图中找到解决方案具有O(n ^ m)的最差情况性能. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |