首页 > 代码库 > 算法5-8:矩形相交
算法5-8:矩形相交
在70年代,计算机已经发展了一段时间,芯片的规模也越来越复杂。因此人们不得不发明一些芯片设计的软件,在软件中完成芯片的设计、调试工作。
当时,模拟运行的时候根据电路的设计,模拟的过程中需要不断地判断矩阵是否相交。那时候还没有很好的算法,人们只能通过暴力手段逐个判断矩阵是否相交。在今天看来,这种算法的复杂度是N^2。根据摩尔定律,计算机CPU每隔18个月,晶体管的数量会增加一倍。由于算法的复杂度是N^2,所以芯片模拟软件的运行时间就要增加3倍!在这种情况下,新的算法诞生了。
算法步骤
首先对矩阵按照横坐标进行排序。类似线段相交问题,做一条扫描线。
当进入矩阵时,在区间树上增加一个区间。
当遇到区间相交的情况时,说明这两个矩阵也是相交的。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。