该算法的时间和空间复杂度是多少?
我计算WC时间复杂度如下:
所有初始化的时间复杂度均为 O(1)
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) .
算法第二部分的时间复杂度如下:
- 启动列表的费用为 1
- for 循环为 17
- 召开 session 的费用为 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;
}
最佳答案
你的最坏情况分析似乎是完全正确的;我没有注意到其中有任何错误,并且得到了相同的结果。
您的最佳情况分析不正确;你说在最好的情况下需要 O(1) 时间,但是你对 meetings
列表的循环总是完成 n 次迭代,所以这种情况也需要 O( n) 时间。您可能会错误地假设列表长度为 1,甚至在最好的情况下为 0;这不算是一个“案例”,因为您需要考虑由大小 n 参数化的一系列输入,以使渐近分析有意义。
你的空间复杂度分析也不正确。您的算法创建两个数据结构:slots
数组具有恒定大小,而 condRange
列表也恰好具有恒定大小,因为它仅从第三个循环附加到,我们已经建立的执行 O(1) 操作,因此向该列表添加操作的数量也是 O(1)。即使此列表最终的大小为 O(n),它也是算法的输出,因此任何正确的算法都必须创建该大小的列表;通常测量“辅助”空间复杂度更有用,即仅用于算法内部工作的临时数据结构使用的空间。
有一个假设需要明确说明,即 session startTime
和 endTime
始终限制在 0 到 16(含)范围内,因此在slots
中用作索引是有意义的。顺便说一句,您不需要为常量 c
发明一个名称,您只需在其中编写 O(1) 即可。
关于java - 该算法的时间和空间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59778513/