Java 中 Math.abs 的时间复杂度？

Question

对于我正在做的作业，我需要确保在 O(n) 时间内有一个算法运行，并且我在一些内部使用了 Math.abs() 函数循环，所以我想知道 Math.abs() 是否在 O(1) 时间内运行？

我认为它会，但我无法在任何地方找到答案。只是想确保我不会在不知情的情况下不小心制作了一个 O(n²) 算法。

Answer 1

Math.abs实现：

public static int abs(int a) {
    return (a < 0) ? -a : a;
}

这将是 O(1) 时间复杂度，因为操作本身是常数时间并且输入是固定的。无论输入什么，操作都会占用保存时间。

循环： O(n)：如果循环变量递增/递减恒定量，则循环的时间复杂度被视为 O(n)。例如，以下函数具有 O(n) 时间复杂度。

   // Here c is a positive integer constant   
   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

Answer 2

这取决于您执行 abs 函数的数据类型：

IEEE754浮点数

abs 表示仅清除保存尾数符号位的 MSB 位。这是对单个放置良好的位的无条件位操作，因此它是 O(1)。这里是 C++ 示例（抱歉不是 JAVA 程序员）
```
float x;         // 32bit variable to perform abs on
int *p=(int*)&x; // this just makes p pointer pointing to x
p[0]&=0x7FFFFFFF;   // clear highest bit by AND
```
非 2'os 补有符号整数类型

这些与上一个项目符号一样具有单独的符号位，因此 #1 中的所有内容也适用于这些。
```
int x;         // 32bit variable to perform abs on
x&=0x7FFFFFFF; // clear highest bit by AND
```
2'os 补充有符号整数类型

abs 对于这些意味着如果设置了 MSB 则取反符号。这意味着您需要对所有位取反。
```
int x;         // 32bit variable to perform abs on
if (int(x&0x80000000)!=0) // negative means MSB is set
 {
 x^=0xFFFFFFFF; // negate all bits
 x++;           // increment
 }
```
这也可以少吃早午餐。无论如何，对于基本数据类型来说，这仍然是 O(1)。但是，如果您开始使用 bigint 或 bigdecimal，则所有位的取反和递增都将变为 O(n)，其中 n 是用于构成数字。 "Digit" 我的意思是什么基数用于内部存储数字。通常它是 2^32 或 2^64 字或 10 的最高幂，可以适合这样的数字。这就是为什么通常最好不要对大数字使用 2'os 补码......（它不仅使 abs 操作复杂化）。

结论

在基本数据类型上，您可以安全地假设 abs 是 O(1) 并且 most 硬件架构支持此操作作为原子指令。

Java 中 Math.abs 的时间复杂度？

Time complexity of Math.abs in Java?

java

math

time

complexity-theory