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

Question

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

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

1. 所有启动均为O（1）

2. for循环为O（n），因为

   • 外循环最多运行n次
   • 启动费用为每人1美元
   • 内循环最多运行17次，以及
   • 国际单项体育联合会的声明和作业每项费用为1美元
   • 我计算O（（n+1+1）*（17+1+1+1+1+1+1+1+1+1+1+1+1），然后忽略常数O（n）

3. 算法第二部分的时间复杂度如下：

   • 启动清单的费用为1
   • 让loop 17岁
   • 会议的启动费用为1
   • 如果报表的成本为1
   • 索引的起始时间为1
   • 对于16岁的人来说
   • 如果语句为1
   • 每项作业1个
   • O（1+（17+1+1+1+1+1+1+1）*（16+1+1+1+1）+1），这只是一个常量，比如说c

4. 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;
    }

Answer 1

你的最坏情况分析似乎完全正确；我没有注意到任何错误，我得到了同样的结果

你最好的案例分析是错误的；你说过在最好的情况下需要O（1）个时间，但是你在meetings列表上的循环总是完成n迭代，所以这种情况也需要O（n）个时间。在最好的情况下，您可能会错误地假设列表长度为1甚至0；这并不算是一个“案例”，因为你需要考虑一系列参数，这些参数的大小是由EM> NE> EEM >进行的。p>

你的空间复杂性分析也不正确。您的算法创建了两个数据结构：slots数组的大小是恒定的，condRange列表的大小也是恒定的，因为它只是从第三个循环中追加的，我们已经建立了第三个循环，它执行O（1）个操作，所以该列表的add操作数也是O（1）。即使这个列表最终的大小为O（n），它也是算法的输出，因此任何正确的算法都必须创建一个该大小的列表；通常，测量“辅助”空间复杂度更有用，即临时数据结构使用的空间，这些临时数据结构只存在于算法的内部工作中

有一个假设可以明确说明，即会议startTime和endTime总是在0到16（包括0到16）的范围内有界，因此在slots中用作索引是有意义的。顺便说一句，你不需要为常数c发明一个名字，你可以在那里写O（1）