这个算法的时间复杂度和空间复杂度是多少？

Question

这个算法的时间复杂度和空间复杂度是多少？

3

这个算法的时间复杂度和空间复杂度是什么？

我将WC时间复杂度计算如下：

1. 所有初始化每个都为O(1) 2. for循环为O(n)，因为： - 外部for循环最多运行n次， - 每个循环的初始化成本为1， - 内部for循环最多运行17次， - if语句和赋值的成本都是1。 - 我计算出O((n+1+1)*(17+1+1+1+1+1+1+1+1+1+1+1+1))，然后忽略常数项O(n)。

3. 第二部分算法的时间复杂度如下： - 初始化List成本为1 - for循环为17 - 初始化Meeting成本为1 - if语句成本为1 - 初始化indexOfEndTime成本为1 - for循环为16 - if语句成本为1 - 赋值的成本都是1。 - O(1+(17+1+1+1+1+1+1)*(16+1+1+1+1)+1)可以简化为一个常数值c。

T(n) = 步骤1 + 步骤2 + 步骤3 = O(1+n+c)，这意味着它的最坏情况时间复杂度是O(n)。这个计算正确吗？你能确认我的每个计算都正确吗？在这种情况下，最好情况的时间复杂度为O(1)？考虑平均情况有意义吗？如果有，如何找到平均情况？

最后，我计算出最好/平均/最坏空间复杂度为O(n)。

    public static List<Meeting> mergeRanges(List<Meeting> meetings) {
        byte available = 0;
        byte reservedBlockStart = 1;
        byte reservedBlockMiddle = 2;
        byte reservedBlockEnd = 3;
        byte[] slots = new byte[17];

        for(Meeting meeting : meetings) {
            byte startTime = (byte) meeting.getStartTime();
            byte endTime = (byte) meeting.getEndTime();
            for(byte i = startTime; i <= endTime; i++) {
                if(slots[i] == available) {
                    if(i == startTime) {
                        slots[i] = reservedBlockStart;
                    } else if(i == endTime) {
                        slots[i] = reservedBlockEnd;
                    } else {
                        slots[i] = reservedBlockMiddle;
                    }
                } else if(slots[i] == reservedBlockStart) {
                    if(i != startTime) {
                        slots[i] = reservedBlockMiddle;
                    }
                } else if(slots[i] == reservedBlockEnd) {
                    if(i != endTime) {
                        slots[i] = reservedBlockMiddle;
                    }
                }
            }
        }

        List<Meeting> condRange = new ArrayList<Meeting>();
        for(byte i = 0; i < slots.length; i++) {
            Meeting meet = new Meeting(0,0);
            if(slots[i] == reservedBlockStart) {
                byte indexOfEndTime = i;
                meet.setStartTime(i);
                for(byte j = (byte)(i + 1); j < slots.length; j++) {
                    if(slots[j] == reservedBlockEnd) {
                        meet.setEndTime(j);
                        indexOfEndTime = j;
                        j = (byte)(slots.length - 2);
                    } 
                }
                condRange.add(meet);
                i = (byte)(indexOfEndTime - 1);
            }
        }
        return condRange;
    }

- PAujla

我只会说它是O(n17) = O(n)。因为第一个循环是n，第二个循环是17个元素，你说它是常数。你要通过这两个循环两次，但是O(2n)与O(n)相同... - emsiiggy

考虑平均情况是否有意义，如果有的话，如何确定？“平均情况”运行时间需要您知道/定义预期看到的输入分布（我相信是作为n的函数）。然后，您可以在给定n的情况下，对输入分布进行平均运行时间计算。 - Kevin Wang

2

在这种情况下，我们可以说最好和最坏的情况都是O（n），因此无论平均分布如何，平均情况也必须是O（n）。@KevinWang - kaya3

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kaya3 · Accepted Answer

您的最坏情况分析似乎完全正确；我没有注意到其中任何错误，而且得到了相同的结果。

您的最佳情况分析是不正确的；您说在最佳情况下它需要O(1)的时间，但是您对meetings列表的循环总是完成n次迭代，因此这种情况也需要O(n)的时间。您可能犯了一个错误，假设列表长度在最佳情况下为1甚至为0；这并不算作一个“情况”，因为要使渐近分析有意义，您需要考虑一个由大小n参数化的输入族。

您的空间复杂度分析也不正确。您的算法创建了两个数据结构：slots数组具有恒定的大小，condRange列表也刚好具有恒定的大小，因为它仅从第三个循环附加，我们已经确定其执行O(1)操作，因此向该列表添加的add操作的数量也是O(1)。即使该列表最终具有O(n)的大小，它也是算法的输出，因此任何正确的算法都必须创建一个该大小的列表；通常更有用的是测量“辅助”空间复杂度，即算法内部运作所需的临时数据结构使用的空间。

有一个假设可以明确说明，即会议的startTime和endTime始终在0到16（包括16）的范围内限制，因此可以在slots中将其用作索引。顺便说一句，您不需要为常量c发明一个名称，您可以只在那里写O(1)。