当前位置：文江博客话题详情

“assoc”的时间复杂度是多少？方案中的函数？

发布于 2024-07-26 02:14:02 字数 31 浏览 2 评论 0原文

这个漂亮的函数“assoc”的时间复杂度是多少？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

屌丝范 2024-08-02 02:14:02

我假设 assoc 是 O(n)*，假设 equal? 在您使用该函数时是 O(1)。这是因为编写您自己的 assoc 版本非常简单：

(define (my-assoc v lst)
  (cond ((null? lst) #f)
        ((equal? v (caar lst)) (car lst))
        (else (my-assoc v (cdr lst)))))

您可以看到它只是在列表 lst 中向下滑动，直到找到匹配项。如果没有找到，则返回#f。

* 技术上等于？ 是 O(n)，其中 n 是较小输入的大小，因此如果您使用 assoc 比较巨大的列表结构，您的运行时间将为 O (n*m)，其中 n 是提供给 assoc 的列表的大小，m 是 v 的大小>。

I would assume that assoc is O(n)*, assuming that equal? is O(1) in your usage of the function. This is because it's trivial to write your own version of assoc:

(define (my-assoc v lst)
  (cond ((null? lst) #f)
        ((equal? v (caar lst)) (car lst))
        (else (my-assoc v (cdr lst)))))

You can see this simply slides down the list lst until a match is found. If none is found, #f is returned.

* technically equal? is O(n) where n is the size of the smaller input, so if you're comparing huge list structures using assoc, your runtime will be O(n*m) where n is the size of the list provided to assoc and m is the size of v.

回复收藏 0 原文

~没有更多了~