算法时间复杂性的对数图/图表
我刚刚编写了快速和合并的排序算法,我想制作其运行时间与数组大小的日志图. 由于我从未做到这一点,我的问题是我选择数组长度的任意数字(输入的大小)是否重要,或者我应该遵循模式(类似于10^3,10^4,10^5,等)? 解决方案 通常,对于每个方法,您需要选择足够大的数组长度,以显示预期的O(n log n)或O(n^2)类型的行为. 如果您的N太小,则运行时间可能由其他增长率主导,例如,运行时间= 1000000*n + n^2的算法对于N 另一方面,如果您的N太大,您的算法可能需要太长完成. 最好的妥协可能是从小N开始,以及N,2N,4N,...或N,3N,9N的时间,并继续增加,直到您可以清楚地看到日志日志图渐变直线.
0 2024-01-23
编程技术问答社区
有没有一种有效的方法来计算log_b(a)的上限?
我需要准确计算 解决方案 您可以使用此身份: b^logb(a) = a 如此二进制搜索x = logb(a)因此,b^x的结果是最大的整数,它仍然小于a,之后只是增加了最终结果. 在这里,32位的小C ++示例: //--------------------------------------------------------------------------- DWORD u32_pow(DWORD a,DWORD b) // = a^b { int i,bits=32; DWORD d=1; for (i=0;i
0 2024-01-23
编程技术问答社区
设计一个Clog n的算法问题[C++代码]
以上升顺序.. 问:设计 O(log N)-time算法,用于找出所有2N整数的中间. n可能无法2 . 要使事情变得容易,我们可以假设O(1)算法返回m,这样: 2^m . 解决方案 您可以使用二进制搜索样式方法在O(logN)时间中解决此问题.考虑以下两个数组: 1 1 2 2 3 1 2 3 4 5 现在合并的中值是: 1 1 1 2 2 2 3 3 4 5 => 2 让我们看看如何找到它.首先猜测中值是每个数组的中心: 1 1 2 2 3 => 2 1 2 3 4 5 => 3 从逻辑上讲,我们知道合并中的中值不能比2或大于3的 大于3. em>这两个值.因此,我们可以在第一个数组中丢弃所有内容 比2较小,第二个数组中的所有内容都比3大.这不会影响中位数的位置,因为我们正在丢弃等
0 2024-01-23
编程技术问答社区
C ++ log2实现用于使用位黑色的双重实现?
我知道我可以在C ++中使用cmath的log2,但我想实现一种有效的学习方式. 我已经看到了很多相关的问题,但是它们都没有给出快速实现,该实现将双精度浮点作为输入,并输出输入的log2近似值为double. . 我想使用位操作来执行此操作,然后我从此答案:: #include #include const double ln2 = log(2); vector log2_float() { int lim = 1 table(lim); for (int i = 0; i LOG2_FLOAT = log2_float(); float f
12 2024-01-23
编程技术问答社区
对数与平方根的大O
一般来说,以下内容总是正确的吗? log(n)= o(n a/(a+1))?英石. a 是任何恒定的正整数,也许很大. 如果不是,则该语句的最大值 a 是什么? 解决方案 随着函数的进行,log( n )总是比 n n 任何功率 n 变大.参见 https://math.stackexchange.com/questions/1663818/do-logarithm-runction-slower-slower-slower-byony-polynomial 用于证明. 这样,只要 a 是一个恒定的正整数,它的价值实际上都无关紧要,因为总是可以找到常数 c 和 k 使log( n ) c ( n a a em>/( a + 1 ) | + k ,这是big-o的定义. 但是,您也可以直观地理解它: n a /( a + 1 )接近 n at a 变大.自然,log( n )始终是o( n ). 其他解决方案 基本事实是,由于对数的凹度,它始终低于其
0 2024-01-23
编程技术问答社区
函数(log n)^k的大O是什么?
对于任何k? 解决方案 运行时具有表单(log n) k 的任何函数为o(((log n) k ).此表达式无法使用简单的转换降低到任何其他原始函数,并且看到具有o(n(n(log n) 2 )之类的runtime算法,这是相当普遍的.这种增长率的功能称为 polygarogarithmic. 顺便说一句,通常(log n) k 写成log k n,因此上述算法将具有运行时O(n log 2 n.在您的情况下,函数log 2 n + log n将为o(log 2 n). 但是,假设k是常数,则具有表单日志的运行时(n k )具有运行时O(log n)的任何功能.这是因为使用对数身份的log(n k )= k log n,而k log n为o(log n),因为k是一个常数.您应该小心不要盲目地得出O(log(n k ))的算法是o(log n);如果k是函数的参数或取决于n,则在这种情况下,正确的BIG-O计算将为O(K log N). 根据您工作的上下文,有时
2 2024-01-23
编程技术问答社区
O(n log log n)时间复杂度
我在这里有一个简短的程序: Given any n: i = 0; while (i we know 2^2^t = 2^2^(t-1) * 2^2^(t-1) T(2^2^t) = T(2^2^(t-1)) + 1=T(2^2^(t-2)) + 2 =.
34 2024-01-22
编程技术问答社区
2的幂的整数的log2
是否有一种有效的方法来找到一个数字的log2,假设它是2的力量.我知道拥有表或 的明显方法 for (log2=0;x!=1;x>>=1,log2++); 但是我想知道是否有更高效/优雅的方式. 解决方案 您只能计算前导或尾随零位的数量,因为任何确切的两个功率都表示为单个1位,其中所有其他位.诸如海湾合作委员会(GCC)等编译器具有这些操作的固有信息,这些操作已汇编为有关适当体系结构的单个指令. 如果您有一个有效的clz(" count铅零"),则A log2实现可能是这样的: int32_t ilog2(uint32_t x) { return sizeof(uint32_t) * CHAR_BIT - clz(x) - 1; } (注意:返回-1 for ilog2(0).) 使用GCC或与GCC兼容的编译器时,您可以像这样定义clz: #define clz(x) __builtin_clz(x) Microsoft也有类似的
18 2024-01-22
编程技术问答社区
对数运算法则
我需要评估任何基础的对数,这并不重要.有算法吗?我在Java中编程,所以我可以使用Java代码. 解决方案 使用此身份: log b (n)= log e (n)/log e (b) 其中log可以是任何基础中的对数函数,n是数字,b是基数.例如,在Java中,这将找到256的基本-2对数: Math.log(256) / Math.log(2) => 8.0 Math.log() Math.log() Math.log() 使用base e.还有其他解决方案 我知道这很晚,但是这可能对某些人有用,因为这里的问题是精确的.一种做到这一点的方法实际上是实现一种从基础中使用的扎根算法,该算法使用您可能想使用的高精度类型,由简单 +-x/operations组成. 我建议实施牛顿的方法,因为它需要相对较少的迭代,并且具有很大的融合.特别是对于这种应用程序,我相信可以说,如果实施良好的输入验证,它将始终提供正确的结果. 考虑一个简单常数的" a" 寻求
2 2024-01-22
编程技术问答社区
O(n)和O(log(n)的区别--哪一个更好,O(log(n)到底是什么?)
这是我在数据结构和每个讲座/TA讲座方面的第一门课程,我们谈论O(log(n)).这可能是一个愚蠢的问题,但是我很高兴有人能向我解释这是什么意思!? 解决方案 这意味着所讨论的事物(通常运行时间)以与其输入大小的对数相一致的方式缩放. big-o norege 并不意味着 centect extcent equarkation ,而是绑定.例如,以下功能的输出为O(n): f(x) = 3x g(x) = 0.5x m(x) = x + 5 因为随着x的增加,它们的输出都线性增加 - 如果f(n)和g(n)之间的比率为6:1,则f(10*n)和g(10*n)之间也将大约有6:1的比率等等. 至于O(n)还是O(log n)更好,请考虑:如果n = 1000,则log n = 3(对于log-base-10).您想运行哪个算法:1000秒或3秒? 其他解决方案 对于简短答案,o(log n)比O(n) 好 现在o(log n)到底是什么?
8 2024-01-22
编程技术问答社区
用常数整除循环计数器的循环的时间复杂度
我正在尝试计算大符号中简单算法的时间复杂性,但其中一部分严重使我的脑海感到困惑.这是算法的简化版本: int a=n while(a>0) { //for loop with time complexity n^3 a = a/8 } 在这种情况下,它是整数部门,因此在A值下降以下.我不确定如何用n表达这一点.我也想知道如何处理这样的未来计算,在这种情况下,循环数量不太容易定义. 解决方案 在这种情况下,我发现以相反的方式更容易.与您在做什么(甚至大约)的相反?类似: for (a = 1; a k
4 2024-01-22
编程技术问答社区
如何非常快地找到二进制对数? (最多是O(1))
是否有任何非常快的方法可以找到整数编号的二进制对数?例如,给定一个数字 X = 5265614583427859334895901384184183521615944777777777777455555555488768必须找到y = log = log = log(x,2),x,2始终是215. x. 问题似乎真的很简单.所需要的只是找到最重要的1位的位置.有一个众所周知的方法地表,但它不是很快,尤其是对于非常长的多字整数. 最快的方法是什么? 解决方案 快速黑客:大多数浮点数表示自动化值,这意味着它们有效地执行循环 Christofferhammarström在硬件中提到了.因此,只要数字在fp表示的指数范围内,就可以简单地从整数转换为fp并提取指数. (在您的情况下,整数输入需要多个机器单词,因此需要在转换中执行多个" shifts".) 其他解决方案 如果整数存储在A uint32_t a[]中,那么我的明显解决方案将如下: 在a[]上运行线性搜索,
0 2024-01-22
编程技术问答社区
`2^n-1`的De Bruijn-like序列:它是如何构建的?
我正在寻找条目 fin o(lg(n))操作中的钻头整数 来自我可以轻松地看到该条目中的第二个算法如何工作 static const int MultiplyDeBruijnBitPosition2[32] = { 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 }; r = MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27]; 计算n = log2 v其中v已知为2的幂.在这种情况下,0x077CB531是普通的de bruijn序列,其余的很明显. 但是,该条目中的第一个算法 static const int MultiplyDeBruijnBitPosition[32] = { 0, 9
0 2024-01-22
编程技术问答社区
什么是O(log* N)?
什么是O(log* n),与O(log n)有何不同? 解决方案 O( log* N )是" 迭代对数": 在计算机科学中,n的迭代对数,书面log* n(通常读取" log star")是对数函数必须在结果小于或等于1之前的对数函数的次数./p> 其他解决方案 log* N位是一种迭代算法,生长非常慢,速度慢得多.基本上,您只能迭代地"记录"答案,直到它低于一个答案(例如:log(log(log(...log(N)))),而您必须log()的次数是答案. 无论如何,这是一个关于Stackoverflow的五年史的问题,但是没有代码?(!)让我们解决这个问题 - 这是递归和迭代功能的实现(它们都给出了相同的结果): public double iteratedLogRecursive(double n, double b) { if (n > 1.0) { return 1.0 + iteratedLogRecursive( Math
2 2024-01-22
编程技术问答社区
表示一个给定的 "int "的最小比特数
在C ++中,找出存储给定的INT需要多少位的最快方法是什么? 我可以尝试多次将数字划分为2个,但分区非常慢.有什么快速的方法吗? 编辑: 非常感谢您的答案.当我说int我的帖子时,我的意思是任何4字节int.例如,如果我存储30665,我想获得15位. 解决方案 您可以通过一半逐渐缩小范围逐渐缩小​​范围. int bits_needed(uint32_t value) { int bits = 0; if (value >= 0x10000) { bits += 16; value >>= 16; } if (value >= 0x100) { bits += 8; value >>= 8; } if (value >= 0x10) { bits += 4; value >>= 4;
4 2024-01-22
编程技术问答社区
对数函数的复杂性是什么?
log base 10 函数的复杂性是什么? 解决方案 这确实取决于要计算对数的值的域. 对于IEEE双打,许多处理器可以在单个组装指令中进行对数;例如,X86具有FYL2X和FYL2XP1指令.尽管通常这样的说明只会在某些固定基础上进行对数,但可以使用 的事实来使用它们在任意基础上进行对数. log a b = log c b/log c a 只需取两个对数并找到它们的商. 对于通用整数(任意精度),您可以使用重复的平方与二进制搜索结合使用,仅使用O(log log n)算术操作进行对数(每次您平方quard a norme a dumears a doup duble the offenend,这意味着您,这意味着您只能在超过其值并进行二进制搜索之前将数字日志n n次保持平衡.使用一些具有fibonacci编号的可爱技巧log n)空间.如果您要计算 binary legarithm 移动以在更少的时间内计算值(尽管渐近复杂性相同). 对于任意
10 2024-01-22
编程技术问答社区
大O记号 对数基数2或对数基数10
文章/问题指出该算法的大运行时间为o(logn). 例如,QuickSort有一个很大的O运行时间O(logn),其中它是log base 10,但二进制树的高度为o(logn+1),其中它是log base 2 问题 1)我对它是log base 10还是log base 2感到困惑,因为不同的文章使用不同的基础来对数. 2)如果其日志库2或日志基础10 ?? ,它会有所不同 3)当我们看到o(logn)??? 时,我们可以假设它是指log Base 10 解决方案 我认为,对日志的基础无关紧要,因为相对复杂性与所使用的基础无关. 因此,您可以将其视为o(log 2 x)= o(log 10 x) 还提到对数与某个常数相关. so log₁₀( x )=log₂( x )/log₂(10) 因此,在大多数情况下,我们通常会在复杂性分析中无视常数,因此我们说基地无关紧要. 您也可能会发现,大多数情况下,基础被认为是2个时间
6 2024-01-22
编程技术问答社区