具有相同任务的单个循环的嵌套循环的时间复杂度是多少

Question

那么，下面给出的两个函数在性能方面有什么区别，两个函数的时间复杂度是多少。它用两个循环和一个循环完成完全相同的任务。

有两个循环。

  RecipeModel returnRecipe(String? suggestion) {
    for (int i = 0; i < _appData.recipeCategories!.length; i++) {
      for (int j = 0; j < _appData.recipeCategories![i].recipes!.length; j++) {
        if (_appData.recipeCategories![i].recipes![j].recipeName! ==
            suggestion) {
          return _appData.recipeCategories![i].recipes![j];
        }
      }
    }
    return recipe;
  }

单循环

RecipeModel returnRecipe(String? suggestion) {
    int recCategoriesLen = _appData.recipeCategories!.length;
    int i = 0
    for (int j = 0; j < _appData.recipeCategories![i].recipes!.length;) {
        if (_appData.recipeCategories![i].recipes![j].recipeName! ==
        suggestion) {
            return _appData.recipeCategories![i].recipes![j];
        }
        j++
        if (_appData.recipeCategories![i].recipes!.length == j && i < recCategoriesLen - 1) {
            i++
            j = 0
        }
    }
    return recipe;
}

Answer 1

当人们第一次学习大 O 表示法时，通常会假设大 O 表示法是通过查看有多少个循环然后以某种方式将这些循环相乘来计算的。虽然情况经常如此，但大 O 分析背后的真正指导原则是从概念上思考循环实际在做什么。

在您的例子中，您有一个由 i 和 j 索引的项目的二维数组。代码的第一个版本显式枚举所有可能的 i 和 j 对，外循环访问 i 的所有选择，内循环访问 j 的所有选择。完成的总工作量与访问的项目数成正比。

第二个循环本质上做同样的事情，但不那么明确。具体来说，它仍然会生成 i 和 j 的所有可能组合，除了只有一个循环驱动 i 和 j 的变化。因为您仍在迭代所有选择，所以完成的工作量可能与您开始时的工作量非常相似。实际性能将取决于 compiler/interpreter 为您所做的优化。

要真正减少您的工作量，您需要找到一种根本不同的策略。由于您要问的问题是“在 i 和 j 的所有组合中，这个项目是否存在？”，您可能想要存储一个辅助散列 table（字典）来存储每个以其名称为键的食谱。这样，您就不需要遍历所有内容，而只需进行字典查找，这样会快得多。

具有相同任务的单个循环的嵌套循环的时间复杂度是多少

What is the time complexity of nested loop over single loop with same task

algorithm

big-o

data-structures