算法5-8:矩形相交
算法 矩形 相交
2023-09-14 09:07:55 时间
在70年代,计算机已经发展了一段时间,芯片的规模也越来越复杂。
因此人们不得不发明一些芯片设计的软件。在软件中完毕芯片的设计、调试工作。
当时。模拟执行的时候依据电路的设计,模拟的过程中须要不断地推断矩阵是否相交。
那时候还没有非常好的算法。人们仅仅能通过暴力手段逐个推断矩阵是否相交。
在今天看来,这样的算法的复杂度是N^2。依据摩尔定律,计算机CPU每隔18个月,晶体管的数量会添加一倍。
因为算法的复杂度是N^2,所以芯片模拟软件的执行时间就要添加3倍!
在这样的情况下。新的算法诞生了。
算法步骤
首先对矩阵依照横坐标进行排序。类似线段相交问题,做一条扫描线。
当进入矩阵时,在区间树上添加一个区间。
当遇到区间相交的情况时,说明这两个矩阵也是相交的。
相关文章
- 操作系统中常用的进程调度算法有_调度算法有哪些
- 前端leetcde算法之--堆
- 使用python的随机森林算法处理遥感数据
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-439 算法训练 简单字符变换
- 高频算法题-两数相加
- 【数据挖掘】关联规则挖掘 Apriori 算法 ( 关联规则简介 | 数据集 与 事物 Transaction 概念 | 项 Item 概念 | 项集 Item Set | 频繁项集 | 示例解析 )
- DeepMind VS Meta:实现纳什均衡理性最优解,还是多人非零和博弈算法更强大?
- 算法-链表中环的入口结点详解编程语言
- 算法-两个链表的第一个公共结点详解编程语言
- 深入串的模式匹配算法(普通算法和KMP算法)的详解