gpt4 book ai didi

big-o - 大哦记法O((log n)^ k)= O(log n)?

转载 作者:行者123 更新时间:2023-12-04 13:42:59 26 4
gpt4 key购买 nike

用big-O表示法是O((log n)^k) = O(log n),其中k是一些常数(例如,循环的对数),是真的吗?

我的教授告诉我,这个说法是正确的,但是他说,这将在类(class)的稍后部分得到证实。我想知道你们中的任何人是否可以证明其有效性或是否有一个链接可以确认它是否正确。

最佳答案

(1)确实O(log(n ^ k))= O(log n)。

(2)O(log ^ k(n))(也写为O((log n)^ k))= O(log n)是错误的。

观察:(1)已被nmjohn证明。

练习:证明(2)。 (提示:f(n)= log ^ 2 n是O(log ^ 2 n)。它是O(log n)吗?是一个足够大的常数c,使得对于所有大于n0的n,c log n> log ^ 2 n?)

编辑:

与此相关的是,任何发现此问题有用和/或有趣的人都应该对新的“计算机科学” StackExchange网站表示热爱。这是一个链接。去使这个新地方成为现实!

http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=rpnXA1_2BNYzXN85c5ibxQ2

关于big-o - 大哦记法O((log n)^ k)= O(log n)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8809252/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com