在学习Cormen的《算法导论》时,我发现了一件奇怪的事情。无论何处,如果它是指单调递增的顺序,这本书都会将其称为“非降序”(non-decreasing)….我的意思是,如果一个系列(2,5,6,3)按“非降序”排列…它不是已经正确了吗?或者,“递增”和“非降”一词的意思相同吗?
在学习Cormen的《算法导论》时,我发现了一件奇怪的事情。无论何处,如果它是指单调递增的顺序,这本书都会将其称为“非降序”(non-decreasing)….我的意思是,如果一个系列(2,5,6,3)按“非降序”排列…它不是已经正确了吗?或者,“递增”和“非降”一词的意思相同吗?
递增 - 1 2 3 4
非递减 - 1 1 2 3
二者的区别在于,对于递增序列中的x(n)和x(n+1),有x(n+1) > x(n),而对于非递减序列中的x(n)和x(n+1),有x(n+1) >= x(n)
是的,
单调递增 == 递增 == 非降序
如果对于所有的a > b,f(a) >= f(b)
严格递增函数 :
如果对于所有的a > b,f(a) > f(b)
1,2,3,4是一个递增序列或非递减序列。
1,1,1,1是一个非递减序列,但不是一个递增序列。
Increasing表示每个元素都比前一个元素大。非递减表示没有任何元素小于它前面的元素,或者换句话说:每个元素都大于或等于它前面的元素。
这取决于作者对这些术语的定义方式。
在您的情况下,作者区分非递减(1、2、2、3)和递增(1、2、3)。在全序的情况下,不是a > b就意味着a <= b,这是有意义的。
其他人称之为递增(1、2、2、3)和严格递增(1、2、3)。在偏序的情况下,对于两个不同的元素a和b,可能既不成立a < b也不成立b < a。
非递减意味着确切的这个。它与递增不完全相同,因为它没有告诉您如何处理相同的值。
考虑序列1, 2, 2, 3, 4。它是一个非递减序列,因为数值按顺序排列,但从一个值到另一个值并不严格增加(即2不大于2)。
这个序列可以像其他人已经解释的那样是递增或递减的,但也可能既不是递增也不是递减。
(1,3,2,4,5,9,1,0)
既不是递增也不是递减。然而,存在像2、4、5、9这样递增的子集或者像9、1、0这样递减的子集。