GA 适应度函数的时间复杂度

Question

我正在尝试为我编写的遗传算法计算适应度函数的时间复杂度。

我做了什么：我已经阅读了一些文章和示例

How to calculate Time Complexity for a given algorithm
Big-O Complexity Chart
Determining The Complexity Of Algorithm (The Basic Part)
How to find time complexity of an algorithm
进化算法的时间复杂度组合优化：十年的成果 .

然而，这些都不是真正令人满意的，我可以说：现在我知道如何在我的代码中应用它了。

让我给你看我的适应度函数，我猜了几个执行时间。

    public static List<double> calculateFitness(List<List<Point3d>> cF, Point3d startpoint)
    {
        List<double> Fitness = new List<double>(); // 1+1
        for (int i = 0; i < cF.Count; i++)  // 1 ; N+1 ; N
        {
            Point3d actual;  // N 
            Point3d next;  // N
            double distance;  // N 
            double totalDistance = startpoint.DistanceTo(cF[i][0]);  // (1+1+1+1)*N
            for (int j = 0; j < cF[i].Count - 1; j++)  // { 1 ; N ; N-1 }*N
            {
                actual = cF[i][j];  // (1+1)*(N-1)
                next = cF[i][j + 1];  // (1+1)*(N-1)

                distance = actual.DistanceTo(next);  // (1+1+1+1)*(N-1)
                totalDistance += distance;  // (1+1)*(N-1)
            }
            totalDistance += cF[i][cF[i].Count - 1].DistanceTo(startpoint);  // (1+1+1+1)*N
            Fitness.Add(totalDistance);  // N
        }
        return Fitness;  // 1
    }

有没有知道链接里有例子的，方便我学习如何面向使用计算时间复杂度。或者也许有人可以在这里解释。例如，对于这段代码，我完全不确定： double totalDistance = startpoint.DistanceTo(cF[i][0]); --> (1+1)N ？或者这样：actual = cF[i][j]; --> (1+1)NN ?

所以一般来说，时间复杂度是：1+1+ (1+N+1+N+N+N+N+4N+ N*{ 1+N+N-1+2*(N -1)+2*(N-1)+4*(N-1)+2*(N-1) } +4N+N) = 2 + (2+14N+ N*{12N-10}) = 12N ^2 + 4N + 4 = O(N^2)

Answer 1

通常在进行 Big-O 分析时，我们会忽略常数时间操作（即 O(1)）和任何常数因子。我们只是想了解算法与 N 的扩展程度。这在实践中意味着我们正在寻找循环和非恒定时间操作

考虑到这一点，我在下面复制了您的代码，然后注释了某些兴趣点。

public static List<double> calculateFitness(List<List<Point3d>> cF, Point3d startpoint)
{
    List<double> Fitness = new List<double>();
    for (int i = 0; i < cF.Count; i++)  // 1.
    {
        Point3d actual;  // 2. 
        Point3d next; 
        double distance;  
        double totalDistance = startpoint.DistanceTo(cF[i][0]);  // 3.
        for (int j = 0; j < cF[i].Count - 1; j++)  // 4.
        {
            actual = cF[i][j];  // 5.
            next = cF[i][j + 1];

            distance = actual.DistanceTo(next);
            totalDistance += distance;
        }
        totalDistance += cF[i][cF[i].Count - 1].DistanceTo(startpoint);
        Fitness.Add(totalDistance); // 6.
    }
    return Fitness;
}

i 循环将执行 N 次，其中 N 是 cF.Count。如果我们非常正式，我们会说比较 i < cF.Count 需要一些常数时间 c 并且 i++ 需要一些常数时间 d。由于它们执行了N次，所以这里的总时间是cdN。但是正如我提到的，Big-O 忽略了这些常数因子，所以我们说它是 O(N).
这些声明是常数时间，O(1)。
索引到 .NET List is documented 为 O(1)。我找不到 DistanceTo 方法的文档，但我无法想象它是 O(1) 之外的任何东西，因为它是简单的数学运算。
这里我们有另一个循环执行N次。如果严格要求，我们会在这里引入第二个变量，因为 cF[i].Count 不一定等于 cF.Count。我不会那么严格的。
同样，对列表进行索引是 O(1)。
这实际上是一个棘手的问题。 Add方法is documented如下：

If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.
- 这通常是如何实现的，大部分时间操作是 O(1)，但偶尔是 O(n) 其中 n 是要添加到的列表的长度，在本例中为 Fitness。这通常被称为amortized O(1).

所以最后你主要只有 O(1) 操作。但是，在另一个 O(N) 循环中有一个 O(N) 循环。所以整个算法是 O(N) * O(N) = O(N²).

GA 适应度函数的时间复杂度

Time Complexity of fitness function for GA

c#

time-complexity

genetic-algorithm