Java'da Math.abs'ın zaman karmaşıklığı?

Question

Yaptığım bir ödev için, O (n) saatinde bir algoritma çalıştığımdan emin olmalıyım ve bazı döngüler içinde Math.abs() işlevini kullanıyorum, bu yüzden Math.abs() O (1) zamanda çalışır?

Bunu düşünürdüm, ama buna bir cevap bulamıyorum. Sadece bilmeden, bir O (n) algoritmasını bilmeden emin olmak istiyorum.

Answer 1

Math.abs uygulaması:

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

işleminin kendisi zaman sabiti ve giriş sabit olduğundan, bu (1) zaman karmaşıklığı O olacaktır. Giriş ne olursa olsun, işlem her zaman kayıt zamanını alacaktır.

Döngü: O (n): Döngü değişkenleri sabit bir miktar artırılır/azaltılırsa, bir döngüde zaman karmaşıklığı O (n) olarak kabul edilir. Örneğin, aşağıdaki işlevler O (n) zaman karmaşıklığına sahiptir. Eğer abs fonksiyonunu gerçekleştiren hangi verilerin türü bağlıdır

// 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 sadece mantis işaret bitini tutan MSB bitinin temizlenmesi anlamına

1. IEEE-754 kayan nokta. Bu, tek bir iyi yerleştirilmiş bit üzerinde koşulsuz bit çalışmasıdır, dolayısıyla O(1). İşte C++ örnek (üzgün değil bir JAVA programcısı)

   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. olmayan 2'os tamamlayacak işaretli tamsayı türleri

   Bunlar sadece önceki mermi gibi ayrı bir işaret biraz var bu yüzden 1. tüm şeyler bunlar için de geçerlidir.

   int x;   // 32bit variable to perform abs on 
   x&=0x7FFFFFFF; // clear highest bit by AND 
   

3. 2'os tamsayı tiplerini bu yollarla için

   absMSB ayarlanırsa işareti olumsuzlamak imzalı kompleman. Bu, tüm bitleri bir artırmayı reddetmeniz gerektiği anlamına gelir.

   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 
   } 
   

   Bu işlem daha az brunch yapılabilir. Neyse temel veri türleri için bu hala O(1). Ancak, bigint veya bigdecimal'u kullanmaya başlarsanız, tüm bitlerin ve artımların her iki şekilde de negasyonu O(n) olur ve n sayıyı oluşturmak için kullanılan "basamak" sayısıdır. "Digit" ile, sayıyı dahili olarak depolamak için hangi bazın kullanıldığı kastediyorum. genellikle bu sayıya sığabilecek 10'un en yüksek 2^32 veya 2^64 sözcük veya en yüksek gücüdür. Bu nedenle, büyük rakamlar için 2'os tamamlayıcısını kullanmamak genellikle daha iyidir ... (sadece abs operasyonunu değil, işini karmaşıklaştırır).

temel veri tipleri üzerinde Sonuç

güvenle en HW mimariler atom talimat olarak bu işlemi destekleyen da absO(1) olduğunu varsayar ve edebilirsiniz.