为什么 findAncestorWidgetOfExactType 是 O(N) 而 dependentOnInheritedWidgetOfExactType 是 O(1)

Question

Flutter中有两个函数：

• findAncestorWidgetOfExactType
• dependentOnInheritedWidgetOfExactType

在文档中，他们说：findAncestorWidgetOfExactType相对昂贵（在树的深度中为O(N) ）。

dependentOnInheritedWidgetOfExactType 的复杂度为O(1)，并且有一个小的常数因子。

任何人都可以解释为什么？为什么第一个比另一个贵？

谢谢

Answer 1

为了回答这个问题并理解为什么两种方法之间的时间复杂度存在差异，我们首先需要澄清两件事：

1-什么是线性搜索？

线性搜索（称为顺序搜索）是一种用于在列表中查找目标值的算法。它按顺序检查列表中每个元素的目标值，直到找到匹配项或搜索完所有元素。

简而言之，O(1) 意味着它需要恒定的时间（例如 10 纳秒）。

另一方面，O(N) 意味着它所花费的时间与集合的大小成线性关系，因此两倍大小的集合将花费两倍的时间。您可能不想将一百万个对象放入其中一个对象中。

因此（ findAncestorWidgetOfExactType ）文档中的提示

“仅当已知此小部件到所需祖先的距离很小且有界时，才调用此方法。”

2- 每种方法搜索的通用“类型”是什么以及在哪里？

• dependentOnInheritedWidgetOfExactType< T 扩展InheritedWidget >
• findAncestorWidgetOfExactType< T 扩展Widget >

考虑到这些，我们可以回答这个问题..那么为什么呢？

因为 findAncestorWidgetOfExactType 方法正在所有的 widget 树中搜索（因为默认情况下它们都是Widget类型）

这是通过线性搜索widgets 树来完成的，因此 => O(N)。

这部分内容已更新，感谢Mabsten 的回答

另一方面，dependOnInheritedWidgetOfExactType不是在部件树中
搜索，而是在包含所有祖先InheritedWidget 的每个 Element 附带的映射中搜索，并按其类型进行索引。

因此，“dependOn”直接从该映射中获取正确继承的小部件，这就是它的复杂度为 O(1) 的原因。

Answer 2

性能的主要差异不是由于findAncestorWidgetOfExactType()搜索任何 Widget 子类，而是dependOnInheritedWidgetOfExactType()仅搜索 InheritedWidget 子类。

dependOnInheritedWidgetOfExactType()_inheritedWidgets成本较低，因为每个小部件（更准确地说，每个元素）都保留所有祖先 InheritedWidget 的Map （在字段中），并按其类型进行索引。然后dependOnInheritedWidgetOfExactType()不在小部件的树中搜索，而仅在此地图中搜索。

有用的文章：

“Flutter InheritedWidget 是如何工作的？”

“Widget - State - Context - InheritedWidget”（作者 Didier Boelens，一篇文章的作者也在 flutter.dev 中引用）