Java中Math.abs的時間複雜度？

對於我正在做的任務，我需要確保我有一個在O（n）時間內運行的算法，並且我在一些循環中使用Math.abs（）函數，所以我想知道是否Math.abs()在O（1）時間運行？Java中Math.abs的時間複雜度？

我會認爲它會的，但我無法在任何地方找到答案。只是想確保我不會意外地在不知道的情況下製作一個O（n ）算法。

2016-03-30 Kane Templeton

從概念上講'Math.abs（）'只是將符號位從負向翻轉爲正向（如果已設置），並且此操作對於任何輸入都應該相似。 –

爲什麼人們否定迴應或問題？我們是否對問題或迴應變得如此不寬容？ – Suparna

我沒有投票，但我可以說，在不顯示努力的情況下提出問題試圖將SO轉換爲Google。 Java的源代碼可用。在一個聲稱讓學生證明運行時間的類中，我期望學生檢查方法調用的源代碼，提供方法調用的正當性（例如Math.abs（））是O（1）（或者任何它是），並且該方法本身是O（n）（或其他）。 – KevinO

的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 
    }

來源

2016-03-30 01:53:20 Suparna

下次您可以嘗試編輯原始答案而不是發佈新答案。 –

我通常會這樣做，但沒有理由，我甚至在完成我的編輯之前發佈代碼時，卻以-3票投票。而且我想要獲得Peer壓力徽章。 :) – Suparna

*「但沒有理由我被打成了-3票」*您的「答案」只是'Math.abs'代碼和「現在自助」，您不知道爲什麼有些用戶低估了這一點？真？ – Tom

這取決於你正在執行什麼數據類型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是用於形成該數字的「數字」的數目。通過「數字」我的意思是什麼基地是用於內部存儲號碼。通常是2^32或2^64單詞或10的最高功率，可以放在這樣的數字內。這就是爲什麼通常最好不要在大數字時使用2's補碼......（這不僅使操作變得複雜）。

結論

在基本數據類型，你可以安全地假設abs是O(1)也是最HW架構支持這個操作，作爲原子指令。

來源

2016-03-31 06:12:58 Spektre

Java中Math.abs的時間複雜度？

回答

相關問題