求数学归纳法 - 腾讯云开发者社区

文章/答案/技术大牛

发布

1回答

证明递归函数的上界复杂度？

recursion、big-o、time-complexity

我很困惑如何用数学归纳法来证明一个递归函数的大O，给出了它的递归关系。示例： T( 1 ) = 1，我们证明了这种递推方法是O(n) = 2n -1，用数学归纳法证明了这一结论。我理解非递归数学归纳法，我们假设n= k，因为它只是变量的变化。那么，为什么假定n=k-1是安全的呢？

浏览 3提问于2014-02-12得票数 2

回答已采纳

1回答

如何用代换法求解() = 2(/2) +1

recursion、time-complexity、big-o、substitution

这里我得到了一个递归函数，我想用替换方法(数学归纳法)来解决这个问题(求出时间复杂度)。在提到的问题中，我们的猜测应该是Ω(log )。实际上，我用数学归纳法证明了T(n) = O(n)，因为n =Ω(log n)，所以T(n)太 .but I没有成功地证明它。我已经看到了这个函数之前的所有答案，但是它们没有用替代方法来解决。

浏览 1提问于2020-10-22得票数 1

2回答

要计算算法的最坏情况运行时间函数，需要遵循哪些步骤？算法

algorithm

我认为这些步骤包括一些数学证明。如果我是正确的，我应该在数学领域的哪些部分很强？(我想数学归纳法、函数、集合就足够了) 谢谢

浏览 1提问于2011-04-13得票数 0

回答已采纳

1回答

计算机编程艺术(第二版)：数学归纳

taocp

在1.2.1数学归纳法一节中，Knuth将数学归纳法作为两个步骤来证明P(n)对于所有正整数n都是正确的： ( b)证明“如果P(1)，P(2)，…，P(n)均为真，则P(

浏览 4提问于2013-03-15得票数 0

回答已采纳

1回答

如何用递归树求解T(n) = T(n-1) + n^2

algorithm、recursion、recurrence

我很难用递归树来解T(n)=T(n-1)+n^2，有人能帮我把图给我，这样我就能很容易理解吗？谢谢。

浏览 1提问于2020-10-11得票数 0

回答已采纳

2回答

归纳法证明背包递推返回最优解

dynamic-programming、knapsack-problem、induction

我必须通过归纳法来证明产生背包问题的最优解(动态规划方法) 我知道数学归纳法是如何工作的，但在这个练习中我被困在了如何做到这一点上。

浏览 16提问于2019-07-09得票数 0

1回答

大O最坏情况的时间复杂度快速排序？

big-o、quicksort

我认为我理解的东西。我不明白的我不太理解的部分是，这是怎样的O(n^2)？就像我知道它至少是O( n^2 )为n+(n-1)+(n-2)+...+2+1 <n^2，但我怎么知道它不是O(n*logn)？我是否需要证明这个结果才能安全地确认它是O(n^2)，还是用一种我看不到的方式立即证明了这一点？我想，一般来说，我怎么知道我找到了代表大O时间

浏览 0提问于2016-06-12得票数 2

回答已采纳

29回答

编程是数学的一个子集吗？

math

我已经听过很多次了，所有的编程都是数学的一个子集。说，OO从根本上讲是基于数学的，但除了一些明显的例子外，我不明白其中的联系：我正在寻找一个可能与企业/OO开发相关的解释，如果有足够强的联系的话。

浏览 119提问于2008-09-26得票数 67

回答已采纳

3回答

有人能解释一下数学归纳法(证明递归方法)吗？

math、recursion

有人能解释一下数学归纳法来证明递归方法吗？我是一名计算机科学专业的大一学生，我还没有上过微积分(我已经上过Trig了)。我有点理解它，但是当我被要求写一个递归方法的归纳证明时，我遇到了麻烦。

浏览 0提问于2009-05-14得票数 8

回答已采纳

1回答

基于旋转的二叉树变换

algorithm、math、data-structures、binary-tree、tree-rotation

在我研究二叉树期中考试的时候，我发现了一条声明，任何任意的n节点二叉树都可以转换成任何其他的n节点二叉树，最多有2*n-2的旋转。有证据证明吗？我找到了某种有渐近符号的证明，但它不是那么清楚。我的意思是，有人能解释/说明为什么是真的吗？如果它说n节点二叉树，它包括根吗？

浏览 6提问于2013-10-28得票数 5

回答已采纳

2回答

数学归纳法，如何证明这个工作在这个递归函数中。

algorithm

return(1) then return(2 · Increment(⌊y/2⌋)) return(y + 1) 所以我必须通过数学归纳法来证明这段代码真的有效以及如何通过数学归纳法来证明这一点。

浏览 4提问于2014-02-06得票数 6

回答已采纳

2回答

解释为什么x == ~(~x + 1) +1(两个补语和后面！)

binary、proof、twos-complement

我想我可以用1位，2位，3位数来证明它，然后使用数学归纳法，但它并不能帮助我理解它是如何工作的。谢谢!

浏览 1提问于2015-11-06得票数 5

回答已采纳

1回答

如何在google地图多边形中放置标记

google-maps-api-3、point-in-polygon

LatLngBounds上的方法getCenter()并不像预期的那样工作，因为多边形的数学中心在视觉上可能不在这个多边形之外。

浏览 3提问于2012-12-27得票数 1

回答已采纳

1回答

归纳在计算密码学中是有问题的--为什么？

complexity、garbled-circuits

在林德尔博士的讲座瑶族建筑及其安全性证明中，他简要地解释了混合论点，他说数学归纳是计算密码学中的一个问题。他解释说，混合论点是“类似”的数学归纳，但不是相同的。据我所知，数学归纳法和混合参数是不一样的，因为对于混合参数，需要有一个有限(k)分布序列才能证明工作(也就是说，最终用最大差* k (可以忽略不计)将k的可忽略差异之和包围起来。

浏览 0提问于2019-06-13得票数 4

回答已采纳

3回答

假设我有下面的递归函数，它返回第n个斐波那契数： if(n == 1) return 0; return fib(n - 1) + fib(n - 2);我该如何编写一段代码来返回此函数进行的递归调用的总数？我在考虑在fib(int n, int count = 0)中引入一个count参数，或者在fib中引入一个静态变量作为static int count = 0，并在递归调用之前递增count。我使用这两种方法都没有成功，因为我不能返回count。有没有办法在不修改原始

浏览 2提问于2016-04-09得票数 1

1回答