小步最短路径算法的时间复杂度，小于等于，Dijkstra最短路径算法的时间复杂度

       华为认为“小步最短路径和Dijkstra在时间复杂度上并没有差异”，下面我给出自己的分析。

      之前只是做了理论的推演，并没真正着手，分析一下小步算法的时间复杂度，这里补课了。

Dijkstra算法时间的复杂度

       时间复杂度考察的是，通过问题规模N和特征量的函数，定性描述算法的运行时间。

       已有时间复杂度的分析方式，给出Dijkstra算法的时间复杂度为 O((|E|+|V|)log|V|) = O((|V|*O(k*averge-degree)+|V|)log|V|) 。Dijkstra算法会无差别的计算，当前节点到邻接节点的路径值。更新次数不会超过|E|，堆高度不会超过log|V|。

      但是这里的“特征量”（如Dijkstra中的log|V|和|E|），在时间复杂度函数中“有效的”必要条件是，问题规模N增长时真实反应开销的增长率。即当N趋于无穷大时，有一关于该特征量的无穷序列，使得0<m<特征量/该序列中的任意项<M，有界。否则，需要把序列中的该项删除，寻找新的特征量，不使用其表示算法的时间复杂度。

|E|分析

       设图节点对应的度序列为d1,d2,d3,...，λi∈(0,1]为di对应节点确定最短路径后需要更新堆的比率。在Dijkstra算法中，随着问题规模N的增长，λidi 只有两种取值可能，不大于K，或是N 趋于无穷大时 lim(λidi/N)在（0,1]。

       当最大的λidi不大于K时，Dijkstra算法的时间复杂度为O((|V|*max(degree)*log|V|)。

       当最大的λidi在N 趋于无穷大时 lim(λidi/N)在（0,1]时，这种情况又分为两个情形。

             即当N趋于无穷时，存在无穷多个这样的λidi，使得 lim(λidi/N)在（0,1]，此时，Dijkstra算法的时间复杂度为O((|V|*max(degree)*log|V|) = O((|V|*|V|*log|V|)。。

            或只有 有限个这样的λidi，此时，Dijkstra算法的时间复杂度为，从度序列中删除这样的di后，余下的di决定算法的时间复杂度为O((|V|*max(degree)*log|V|)。

log|V|分析

      设d[i]=do[i]+di[i]，d[i]为第i个节点的度，do[i]为第i个节点在一次最短路径查询中比其最短路径值大的邻接节点的数量（路径出度），do[i]为第i个节点在一次最短路径查询中比其最短路径值小的邻接节点的数量（路径入度），i 的升序表示节点获得最短路径的顺序。

      在第n次迭代后，堆中节点数量 = | ∪ no[i] | - n ∈ [0,N-1]，已确定最短路径的节点数量为n，i ∈[0,n]，n ∈[0,N]，do[0]=1，di[0]=0，do[N]=0，no[i] 为第i个节点在一次最短路径查询中比其最短路径值小的邻接节点，ni[i] 为第i个节点在一次最短路径查询中比其最短路径值大的邻接节点。

      设do[i]=| ∪ no[i] |为常量o，在堆节点扩张阶段no[i]中不在堆中节点的概率为λ1∈ (0,1]，在堆节点收缩阶段no[i]中不在堆中节点的概率为λ2∈ (0,1]，λ1 > λ2。堆中节点数量在一次查询中，先扩张，后收缩。

      在第n次迭代后，堆中节点数量 = λ1 * n*o - n   = n * (λ1 *o - 1), 又n ∈[0,N-1]。因此，log|V|在时间复杂度中是合理的。

     综上所述，Dijkstra算法的时间复杂度，依赖于图的复杂性，即边集E的复杂性和顶点集V的规模。

      https://inst.eecs.berkeley.edu/~cs61bl/r//cur/graphs/dijkstra-algorithm-runtime.html?topic=lab24.topic&step=4&course=

小步算法

       Dijkstra算法时间复杂度中的|E|和log|V|，取值过于宽泛，并不适用于小步算法。

       在小步算法中，在任意时刻，只考察，确定最最短路径且有未处理邻接边的节点的，权重值最小的未处理邻接边。这种懒处理的方式，会使得更多的邻接边在考察之前，其两个端节点就都确定了最短路径，降低了堆中节点的数量以提高堆的成本，避免了更多无效路径值的计算以节省计算资源（节点只有两种状态，即确定了最短路径的节点和未确定任何路径的节点），避免了无效的节点路径值的更新以提高程序的并行能力。       

        与|E|一样，log|V|对于小步算法而言也是不合理的。设图G1上节点p1到其它节点的最短路径值都不一样，确定邻接节点的最短路径时，小步算法只会把该邻接节点加入到堆中，堆的增长速度与节点的度无关。节点邻接边权重差异越大时，小步算法优势愈大。Dijkstra算法取最大值log|V|同样不适合于小步算法。

时间复杂度

       小步最短路径算法中，关于维护堆相关的时间复杂度，与顶点集无关，与边集的复杂性无关，至少不直接相关。

      设小步最短路径算法，在一次查询中得到的，以节点p1为根的最短路径树为T；

      设小步最短路径算法，在该次查询中，按照节点确定最短路径的先后顺序构成的节点序列为p1p2p3...pN，节点pi对应的最短路径值为li；

      设小于等于li的最短路径值的节点中，存在邻接节点的最短路径值大于li的数量为ci，

      则，小步算法的时间复杂度为，O( |E| + ∑logci )，其中|E|为边集访问的复杂性，是没法避免的。

      又因为，小步最短路径算法，可在每次迭代中，只确定一个节点的最短路径，至多向堆中增加一个节点，至多从堆中删除一个节点，所以存在一个ci的序列，cj，使得cj<=cj+1，小步算法的时间复杂度为<=O( |E| + N*log(max(ci)) )。

      上述复杂度O( |E| + ∑logci )存在一个假设，即在确定一个节点的最短路径后，只是在删除、更新、添加节点到堆中时，才有lg(ci) 的操作需要。但是，不同的堆中节点的下个待处理最近邻接节点可能是同一节点，需要堆操作的次数1<=R(li)<ci，R(li)为当确定节点的最短路径最大为 li 时需要调整堆的次数。

      因此，小步算法的时间复杂度为O( |E| + ∑( R(li) * logci ) ) 。

      又R(li) * logci < R(li) * logN ，∑(R(li)) < ∑(do(i))

              有 O( |E| + ∑( R(li) * logci ) ) <= O(  |E| +  logN*∑(R(li))  ) <= O(( |E| +|V|)log|V|) 。

     小步最短路径算法的复杂性，在 log|V| 和 |E|的基础上进一步缩小，

     与遍历图所得到的以起点为根的最短路径树的复杂度有关，

     与最短路径树的子树间的复杂度，即R(li)，有关。

     华为认为“小步最短路径和Dijkstra在时间复杂度上并没有差异”。但本文认为，小步算法的时间复杂度，会大概率比Dijkstra的时间复杂度要小，甚至小很多，且在工程上会有很大的提升，有很大价值。