在我的人工智能入门课程中，我们研究了几种不同的搜索算法及其属性。在分析它们的空间和时间复杂度时，我们会制定一个大 O 复杂度，它就树本身的属性而言（例如，分支因子 b 或最浅解的深度 d）。
我的问题是，以这种方式定义时间和空间复杂度似乎完全没有用，因为我们首先寻找解决方案的全部目的是因为我们不知道树/解决方案的本质（通往解决方案的路径）它有多浅，等等）。因此，根据我目前的理解，这种形式的时间/空间复杂性分析并没有为必须为搜索问题选择算法的人提供一种有意义的方法来辨别哪个算法更好（就时间/空间复杂性而言）。
时间和空间复杂性分析通常是一个非常棘手的野兽。
在过去的几十年里，最坏情况分析是推断运行时间和空间需求的有用工具。然而，事实证明，最坏情况分析往往与我们在现实中观察到的情况相矛盾。这推动了对更好的复杂性分析类型的搜索。目前最常见的是平均情况和细粒度复杂性。
在平均情况下，我们不会寻找最坏的情况，而是尝试描述平均情况，从而进行大量统计分析和随机分析来定义此类实例的外观以及它们具有哪些属性。
在细粒度的复杂性中，我们尝试将所有输入实例的范围分成具有不同属性的多个类别，并分别分析它们的复杂性。一个更温和的版本是引入实例的附加参数，以便能够显示算法之间的差异。
因此，即使您不确切知道特定实例中的参数是什么，您也许可以找到一些界限。
举个例子：假设您有多种算法来在未排序的数据堆中查找项目，并且所有算法都具有相同的最坏情况时间和空间复杂度。但当你仔细观察时，你会发现有些在输入大小方面具有非常好的平均复杂度。如果搜索项的位置具有某些属性，则可能有些具有恒定的时间复杂度。这些信息非常有用，因为在实践中问题常常伴随着许多额外的结构。
但是，最终总是必须针对给定的用例测试算法。例如。如果您想要对存储在硬盘上的 5 TB 数据进行排序，您会发现快速排序是一个非常糟糕的选择，您应该使用一些实现某种多路合并排序的外部内存库。如果你想对最多 10 个元素的小列表进行排序，使用冒泡排序可能比合并排序或快速排序更快。
引用@Matt Timmermans 上面的评论来回答我的问题：
“...您通常会对平均分支因子有一个期望，m 将是您根据搜索算法的复杂性选择的值。即，“探索树的多少部分是实用的”。
根据我的理解（也来自@AbcAeffchen的答案），我们估计 b 和 m 等变量的值，以尝试针对我们的树进行估计，这样我们就不必依靠最坏情况分析，而许多情况下时代并不反映现实。这为我们提供了更细粒度的估计。然而，我们不会关心 b 和 m 的实际值。