給出一個列表中的數字。如何用最小的時間複雜度來代替每個元素

我已經編寫了一個java程序，它通過一些常量清單中的每個數字。以下是該計劃。我已經創建了一個myNewNumbers列表來存儲這些多個數字。下面是我的疑惑給出一個列表中的數字。如何用最小的時間複雜度來代替每個元素

有沒有更好的方式來寫在最小的時間複雜度？目前在我的for循環中有10個元素。如果用戶想要處理100萬個元素，該如何處理？我是初學者多線程。如何確保它在mutithreading

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 

public class MultiplyHugeNumber { 

    static List<Integer> mynumbers; 
    static List<Integer> myNewnumbers; 
    static Integer MUTIPLY_ELEMENT=2; 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 

     mynumbers= new ArrayList<Integer>(); 
     for (int i = 0; i < 10; i++) { 
      mynumbers.add(i); 
     } 

     System.out.println(Arrays.toString(mynumbers.toArray())); 
     myNewnumbers= new ArrayList<>(); 
     for (Integer mynumber : mynumbers) { 
      myNewnumbers.add(mynumber*MUTIPLY_ELEMENT); 

     } 

     System.out.println(Arrays.toString(myNewnumbers.toArray())); 
    } 

o/p:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

來源

2016-05-11 shreekanth

哦，看，過早的優化。我們生活在2016年，而不是1980年，您的電腦可以處理幾百萬次的乘法運算。 –

多線程與時間複雜性無關。無論是否使用多個線程，您都必須處理所有元素，因此您的時間複雜度將爲'O（n）'。可能你正在將它與並行處理混合在一起，以減少執行的總時間。 – STaefi

（學分@STaefi）的恆定值乘以輸入值的名單的O(n)一個時間複雜度。這種複雜性與多線程實現無關。

你的程序：由一個常量落在乘號碼列表成所謂"Embarrassingly Parallel"問題類別：

「[...]一個在需要很少或根本沒有力氣的問題分成並行任務數「

輸入列表中的每個項目都可以與常數相乘，而不涉及任何其他輸入項目或全局狀態。

有多種方式可以並行化給定的任務。請注意，設置線程的開銷可能不適合少量的輸入值，或者完全可以在這個特定的示例中使用。使用Java 8流

例子：

mynumbers.parallelStream() 
      .map(in -> in * MUTIPLY_ELEMENT) 
      .collect(Collectors.toList());

來源

2016-05-11 06:30:02 reto

這是100％過早的優化，也很可能沒有優化值得的在這種情況下。

但是，純粹從學術上講，你需要在這裏問自己一個問題，即結果的順序是否重要？

如果沒有，那麼有流，這很簡單，這裏的有100個號碼的例子：

Integer MUTIPLY_ELEMENT = 2; 
    List<Integer> resultNumbers = IntStream.range(0,100) 
      .parallel() 
      .map(i->i*MUTIPLY_ELEMENT) 
      .boxed() 
      .collect(Collectors.toList());

如果你不關心訂購，但仍想獲得並行處理的好處，你可以採取優勢在於您的操作（乘以2）足夠簡單，以至於所得數字仍然處於相同的相對「自然」順序，並且只需在呼叫map()後的流上呼叫sorted()即可。但是，排序操作可能會很長，只要你只是單線程就可以。

另外，要明白，這是沒有意義的「真實世界」的情況下，你幾乎從不會遇到像這樣的實際問題。希望你只是試圖讓你的頭部平行於總體，因爲在嘗試單線程模型之前，你永遠不會想要進行這種類型的優化，並且它證明不足。

來源

2016-05-11 06:33:18

如果您有一百萬個元素，並且您需要將每個元素乘以一個常量，那麼您將需要執行一百萬次操作。這是沒有辦法的 - 它是O（n）。

也就是說，創建列表可以是O（1）（恆定時間），如果你沒有懶惰評估列表。番石榴的Lists.transform做到了這一點：

List<Integer> myNumbers = ... 
List<Integer> myNewNumbers = Lists.transform(myNumbers, i -> i * MULTIPLY_ELEMENT);

這不會減少它需要做的所有乘法的總時間;實際上，它可能需要更多時間，因爲JVM難以優化。如果您多次訪問相同的元素，它也會變慢，因爲轉換將在您每次執行時應用。也就是說，它不太可能會因爲你會注意到的數量而變慢。

此方法還帶有限制，即您無法向轉換的列表添加新元素（如JavaDocs中所述）。但是，根據您的情況，可能還有其他好處可以讓您快速創建初始列表。

來源

2016-05-11 06:35:35 yshavit

給出一個列表中的數字。如何用最小的時間複雜度來代替每個元素

回答

相關問題