圈复杂度(复杂度)

Question

我有一个寻找最短距离/路径的程序，我得到了一个正确的答案，但我得到了一个问题，即“函数'shortestPath‘的复杂性为9，允许的最大值为6。”这就是算法：

const graph = {
  start: { A: 5, D: 8 },
  A: { B: 9, C: 3 },
  D: { C: 4, E: 6 },
  C: { B: 5, E: 2 },
  B: { end: 7 },
  E: { end: 4 },
  end: {}
};

function shortestCostNode(costs, processed) {
  return Object.keys(costs).reduce((lowest, node) => {
    if (lowest === null || costs[node] < costs[lowest]) {
      if (!processed.includes(node)) {
        lowest = node;
      }
    }
    
    return lowest;
  }, null);
}

// this function returns the minimum cost and path to reach end
function shortestPath(graph) {
  // track lowest cost to reach each node
  const costs = Object.assign({ end: Infinity }, graph.start);
  
  const parents = { end: null };
  
  for (let child in graph.start) {
    parents[child] = 'start';
  }
  
  const processed = [];
  let node = shortestCostNode(costs, processed);
  
  while (node) {
    let cost = costs[node];
    let children = graph[node];
    
    for (let n in children) {
      if (children.hasOwnProperty(n)) {
        let newCost = cost + children[n];
        
        if (!costs[n] || costs[n] > newCost) {
          costs[n] = newCost;
          parents[n] = node;
        }
      }
    }
    
    processed.push(node);
    node = shortestCostNode(costs, processed);
  }

  let optimalPath = ["end"];
  let parent = parents.end;
  
  while (parent) {
    optimalPath.push(parent);
    parent = parents[parent];
  }
  
  optimalPath.reverse();

  const result = {
    distance: costs.end,
    path: optimalPath
  };
  return result;
}

如何降低函数shortestPath的复杂度？

Answer 1

圈复杂度

是对通过某些代码的可能路径数的度量。例如，带有一个子句的if语句(如if (foo) {} )有两条路径，一条如果foo为true，另一条为false。代码可以分支的任何点，分支都被计算为圈复杂度的一部分。

不幸的是，复杂性的求和方式是不同的，所以不知道度量是如何计算的，所以没有简单的方法来给出答案。您能做的最好的就是减少代码中可能的分支数。

改进代码

看看您的代码，就会有足够的空间来减少分支的数量。

由于节点中最短的链路对最终结果没有影响，因此不需要函数shortestCostNode。最短的链接很可能使你走上最长的一条路。搜索最短链路对节点的顺序选择没有任何改善。

shortestCostNode是解决方案复杂性的主要来源，它有效地将搜索随机化。正因为如此，你必须跟踪你走过的路径，这样你就不会重复同样的路径，这就增加了很多负担。

如果您系统地按顺序搜索所有可能的路径(跟踪未到达的位置)，则无需跟踪您所在的位置，因此可以删除大量代码。

使用堆栈搜索树

因为搜索最短路径需要沿着路径旅行，然后回溯到最近的未移动分支，因此堆栈是跟踪进度的最佳方法。

从节点开始，将所有路径和成本推送到堆栈中，然后弹出一条路径并沿着该路径移动到下一个节点，同时添加成本。然后对下一个节点执行相同的操作。

当您到达终端节点时，您将检查距离，如果它是迄今为止最短的，则保存该距离和所走过的路径。然后从堆栈中弹出下一个路径步骤，直到检查完所有路径为止。

递归堆栈

实现堆栈的最简单(但不是最快的)方法是通过递归。

因此，您将得到一个函数，类似于

function shortestPath(graph) {
    const result = {distance: Infinity}, endName = "end";
    function followPath(node, totalDist = 0, path = ["start"]) {
        for (const [name, length] of Object.entries(node)) {
            const distance = totalDist + length;
            if (distance < result.distance) {
                if (name === endName) {  
                    Object.assign(result, {distance, path: [...path, endName]}); 
                } else {
                    path.push(name);
                    followPath(graph[name], distance, path);
                    path.pop();
                }
            }
        }
    }
    followPath(graph.start);
    return result;
}

该函数的圈复杂度约为5。

注意，函数只遵循路径，而所走的距离小于已经找到的最短路径。这意味着您可能不需要检查到结束的所有路径。

还有很大的改进空间(在复杂性和性能方面)，但是由于您还没有对图的可能结构进行太多的定义，所以没有进一步的意义。

Answer 2

const诉let

首先，我想为const在某些地方的使用而鼓掌。然而，有一些地方可以使用const而不是let --例如用于optimalPath，因为它永远不会被重新分配。建议默认使用const，然后在需要重新分配时切换到let。这有助于避免意外重新分配和其他错误。

添加到optimalPath

中

不需要调用push()将项添加到optimalPath，然后调用reverse，而是可以使用unshift()方法将项添加到数组的开头，从而消除了逆转数组的需要。

迭代在shortestCostnode()

中

注意Array.prototype.reduce() - for参数initialValue的MDN文档。

initialValue Optional 用作callback第一个调用的第一个参数的值。如果没有提供initialValue，则数组中的第一个元素将用作初始accumulator值，并跳过为currentValue。在没有initialValue的空数组上调用reduce()将引发一个TypeError。

这意味着，与其将null传递给初始值，还可以省略该值，以便将第一个值用作lowest的初始值，并且它将跳过第一次迭代。这样就不需要在lowest === null条件下检查if了。

记忆

一种可能的优化方法是回溯结果--例如，如果shortestCostNode()被调用时带有重复的参数，那么就可以存储计算出来的返回值，这样就可以在后续的调用中查找并返回它，而无需重新计算该值。

迭代子项

对于while循环中的循环

用于(让n人在儿童中){

      if (children.hasOwnProperty(n)) {

考虑使用for...of循环与Object.entries(children)相结合

然后，不需要检查属性是否存在于children中(而不是原型链的更高部分)。

for (const [n, child] of Object.entries(children)) {

它使用const而不是‘`let’，因为不需要在循环中重新分配值。

n的一个更合适的名称是key：

for (const [key, child] of Object.entries(children)) {