如何修改 O(n) 列表长度函数以在 O(1) 中运行？
从这个链接，是文件 ilist.c 的副本 http://www.student.cs.uwaterloo.ca/~cs136/ assignments/a5/
我需要做的是如何转换这个 O(n) 函数以在 O(1) 中运行：
// computes the number of elements in il
int ilength(ilist il)
{
int i = 0;
while (!iempty_huh(il))
{
i++;
il = irest(il);
}
return i;
}
我可以编辑 ilist.c 文件中的函数（我假设结构和图标）但我无法编辑 ilist.h 文件。我根本不知道如何转换为 O(1) ，任何想法都会有帮助！
From this link, is a copy of the file ilist.c
http://www.student.cs.uwaterloo.ca/~cs136/assignments/a5/
What i need to do is how to convert this O(n) function to run in O(1):
// computes the number of elements in il
int ilength(ilist il)
{
int i = 0;
while (!iempty_huh(il))
{
i++;
il = irest(il);
}
return i;
}
I can edit functions in the ilist.c file (im assuming the struct and icons) but i can't edit the ilist.h file. I don't know how to approach the conversion to O(1) at all, any ideas, would be helpful !
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您可以将列表中的元素数量存储在与其关联的对象中，随着每个添加的元素而增加它，并随着每个删除的元素而减少它。然后，如果请求列表的总长度，您只需返回该数字。
我没有看到任何其他方法可以做到这一点。遍历链表总是需要 O(n)。
You can just store the number of the elements in the list in the object associated with it, increase it with every added element, and decrease it with every deleted element. Then, if the total length of the list is requested, you just return that number.
I don't see any other way of doing that. Traversal of a linked list always requires O(n).
相应更改的函数：
icons、ilength。Functions to change accordingly:
icons,ilength.作为提示，如果您更新了列表，以便每当您对其执行操作时它都会预先计算长度，会怎么样？这样，您就可以让长度以 O(1) 的形式返回预先计算的值。
As a hint, what if you updated the list so that it precomputes the length whenever you do an operation on it? That way, you could have the length just return the precomputed value in O(1).
关键是您可以在 ilist.h 的界面后面存储额外的信息 - 考虑在添加和删除元素时维护元素计数作为列表的一部分。然后只需返回 ilength 的计数即可。
The key is that you are allowed to store extra information behind the interface in ilist.h - think about maintaining a count of elements as a part of the list as you add and remove them. Then just return the count for ilength.
如果您在构建 ilist 时跟踪 ilist 的大小，则可以在 O(1) 中返回已知的大小。
If you keep track of the size of ilist when you build it you can just return the already known size in O(1).