java - 该算法的时间和空间复杂度是多少？

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

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

每一个

的所有引发都是O(1)

将循环设为O(n)，因为

external for循环最多运行n次，

引发成本为每个

1

inner for循环最多运行17次，而

if语句和赋值的成本均为1。

我计算O((n + 1 + 1)*(17 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1)，然后忽略常数O(n)。

算法第二部分的时间复杂度如下:

列表的初始化为成本1

将循环设为17

会议的召开费用为1

如果语句的成本为1

将indexOfEndTime初始化为1

将循环设为16

如果语句为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;
    }

最佳答案

您的最坏情况分析似乎是完全正确的。我没有发现任何错误，并且得到了相同的结果。

您的最佳情况分析不正确；您说最好的情况下需要花费O(1)时间，但是在meetings列表上的循环总是完成n次迭代，因此这种情况下也要花费O(n)时间。您可能会犯一个错误，即在最佳情况下假定列表长度为1甚至0。这并不算作“案例”，因为您需要考虑使用大小为n的参数来进行渐进分析，这样才有意义。

您的空间复杂度分析也不正确。您的算法会创建两个数据结构:slots数组的大小恒定，并且condRange列表的大小也恒定，因为它仅从第三个循环中追加，我们已经建立了O(1)操作，因此该列表的add操作数也为O(1)。即使该列表最终的大小为O(n)，它也是算法的输出，因此任何正确的算法都必须创建该大小的列表。通常，测量“辅助”空间复杂度(即仅用于算法内部工作的临时数据结构使用的空间)更有用。

有一种假设可以明确地进行陈述，那就是会议startTime和endTime始终限制在0到16(含)范围内，因此在slots中用作索引是有意义的。顺便说一句，您不需要为常量c命名，只需在其中写O(1)即可。