一个“非递减”序列是否就是“递增”的？

Question

在学习Cormen的《算法导论》时，我发现了一件奇怪的事情。无论何处，如果它是指单调递增的顺序，这本书都会将其称为“非降序”（non-decreasing）….我的意思是，如果一个系列（2,5,6,3）按“非降序”排列…它不是已经正确了吗？或者，“递增”和“非降”一词的意思相同吗？

- Vaibhav

---

非递减意味着每个后续元素都不小于前一个，而递增则意味着每个后续元素都大于前一个。 - giolekva

这是一个语言问题，而不是编程问题。 - isekaijin

非递减并不意味着不增加。同样地（但以不同的方式），非线性并不意味着不是线性的。而（以另一种不同的方式）非负并不意味着不是负数。在英语中，“非”是一个具有欺骗性的后缀，会产生相当多的无意义内容，因此用欧拉-文图表为这三种不同情况绘制它们是一个很好的练习。 - Oskar Limka

Answer 1

递增 - 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)

- danben

---

此答案与常见的数学术语不同。请参见下面的Kunal Vyas答案。 - Yola

@Yola - “与常见数学术语不一致”是什么意思？你的意思是这个答案在数学上是错误的吗？ - MasterJoe

Answer 2

是的，

单调递增 == 递增 == 非降序

如果对于所有的a > b，f(a) >= f(b)

严格递增函数 :

如果对于所有的a > b，f(a) > f(b)

- Kunal Vyas

---

这个答案必须被接受，因为它提供了数学术语。 - Yola

如果有一个例子，这个答案会更好。 - MasterJoe

根据https://mathworld.wolfram.com/MonotoneIncreasing.html的说法，“单调递增：始终增加；永不保持不变或减少。也称为严格递增。”（也许“错误”） - Mingwei Samuel

@Yola 但更普遍的是，人们使用“非递减”而不是“递增”的原因是为了避免在计算机科学和数学中的歧义。 - Mingwei Samuel

Answer 3

1,2,3,4是一个递增序列或非递减序列。

1,1,1,1是一个非递减序列，但不是一个递增序列。

- cletus

---

这个答案与常见的数学术语不同。请参考下面的Kunal Vyas答案。 - Yola

Answer 4

Increasing表示每个元素都比前一个元素大。非递减表示没有任何元素小于它前面的元素，或者换句话说：每个元素都大于或等于它前面的元素。

- sepp2k

Answer 5

如果在系列中有重复项，那么使用术语“非递减”比“递增”更加准确。

- xpda

Answer 6

这取决于作者对这些术语的定义方式。

在您的情况下，作者区分非递减（1、2、2、3）和递增（1、2、3）。在全序的情况下，不是a > b就意味着a <= b，这是有意义的。

其他人称之为递增（1、2、2、3）和严格递增（1、2、3）。在偏序的情况下，对于两个不同的元素a和b，可能既不成立a < b也不成立b < a。

- starblue

Answer 7

非递减意味着确切的这个。它与递增不完全相同，因为它没有告诉您如何处理相同的值。

考虑序列1, 2, 2, 3, 4。它是一个非递减序列，因为数值按顺序排列，但从一个值到另一个值并不严格增加（即2不大于2）。

- Jeff Paquette

Answer 8

这个序列可以像其他人已经解释的那样是递增或递减的，但也可能既不是递增也不是递减。

(1,3,2,4,5,9,1,0)

既不是递增也不是递减。然而，存在像2、4、5、9这样递增的子集或者像9、1、0这样递减的子集。

- Victor Hurdugaci