最常見的Java常見面試題問答(3)_面試精選

最常見的Java常見面試題問答(3)

發表于：2013-01-24來源：ImportNew作者：不詳點擊數：標簽：java

只要數據元素的關系可以表示成節點和邊的網狀結構的話，就可以用圖來表示。樹是一種特殊的圖，它的所有節點都只能有一個父節點。和樹不同的是，圖

　　只要數據元素的關系可以表示成節點和邊的網狀結構的話，就可以用圖來表示。樹是一種特殊的圖，它的所有節點都只能有一個父節點。和樹不同的是，圖的形狀是由實際問題或者問題的抽象來決定的。例如，圖中節點(或者頂點)可以表示不同的城市，而圖的邊則可以表示兩個城市之間的航線。

　　在Java里構造一個圖，你需要解決數據通過什么方式保存和訪問的問題。在圖里面也會用到上面提到的數據結構。Java的API里沒有提供圖的實現。不過有很多第三方庫里提供了，例如JUNG，JGraphT，以及JDSL(不過好像不支持泛型)?！禖ore Java Career Essential》一書包含了用Java實現的可用示例。

　　Q:你對大O這個符號有什么了解呢，你是否可以根據不同的數據結構舉出一些列子來?

　　A：大O符號可以表示一個算法的效率，也可以用來描述當數據元素增加時，最壞情況下的算法的性能。大O符號也可以用來衡量的性能，例如內存消耗量。有時候你可能會為了減少內存使用量而選擇一個比較慢的算法。大O符號可以表示在大量數據的情況下程序的性能。不過，對于程序在大量數據量下的性能的測量，唯一比較實際的方式是行用較大的數據集來進行性能基準測試，這樣可以把一些在大O復雜度分析里沒有考慮到的情況包含進去，例如在虛擬內存使用比較多的時候系統會發生換頁的情況。雖然基準測試比大O符號表示的結果更加實際，但是它不適用于設計階段，所以在這個這時候大O復雜度分析是最合適的選擇。

　　各種數據結構在搜索，插入和刪除算法上的性能都可以用下面方式表示：常量復雜度O(1)，線性復雜度O(n)，對數復雜度O(log n)，指數復雜度O(c^n)，多項式復雜度O(n^c)，平方復雜度O(n^2)以及階乘復雜度O(n!)，這里面的n都指的是數據結構里的元素的數量。性能和內存占用是可以相互權衡的。下面是一些示例。

　　示例1：在HashMap里查找一個元素的的時間復雜度是常量的，也即是O(1)。這是因為查找元素使用的是哈希函數，并且計算一個哈希值的時間是不受HashMap里的元素的個數的影響的。

　　示例2：線性搜索一個數組，列表以及鏈表都是的復雜度線性的，也即是O(n)，這是查找的時候需要遍歷整個列表。也就是說，如果一個列表的長度是原來的兩倍，那么搜索所花的時間也是原來的兩倍。

　　示例3：一個需要比較數組里的所有元素的排序算法的復雜度是多項式的，即是O(n^2)。這是因為一個嵌套的for循環的復雜度是O(n^2)。在搜素算法里有這樣的例子。

　　示例4：二分搜索一個數組或者數組列表的復雜度是對數的，即是O(log n)。在鏈表里查詢一個節點的復雜度一般是O(n)。相比較數組鏈表和數組的O(log n)的性能而言，隨著元素數量的增長，鏈表的O(n)的復雜度的性能就比較差了。對數的時間復雜度就是如果10個元素花費的時間是x單位的話，100個元素最多花費2x單位的時間，而10000個元素最多花費4x個單位的時間。如果你在一個平面坐標上畫出圖形的話，你會發現時間的增長沒有n(元素的個數)快。

　　Q：HashMap和TreeMap在性能上有什么樣的差別呢?你比較傾向于使用哪一個?

　　A：一個平衡樹的性能是O(logn)。Java里的TreeMap用一個紅黑樹來保證key/value的排序。紅黑樹是平衡二叉樹。保證二叉樹的平衡性，使得插入，刪除和查找都比較快，時間復雜度都是O(log n)。不過它沒有HashMap快，HashMap的時間復雜度是O(1)，但是TreeMap的優點在于它里面鍵值是排過序的，這樣就提供了一些其他的很有用的功能。

　　Q：怎么去選擇該使用哪一個呢?

　　A:使用無序的HashSet和HashMap，還是使用有序的TreeSet和TreeMap，主要取決于你的實際使用場景，一定程度上還和數據的大小以及運行環境有關。比較實際的一個原因是，如果插入和更新都比較頻繁的話，那么保證元素的有序可以提高快速和頻繁查找的性能。如果對于排序操作(例如產生一個報表合作者運行一個批處理程序)的要求不是很頻繁的話，那么把數據以無序的方式存儲，然后在需要排序的時候用Collections.sort(…)來進行排序，會比用有序的方式來存儲可能會更加高效。這個只是一種可選的方式，沒人能給你一個確切的答案。即使是復雜度的理論，例如O(n)，成立的前提也是在n足夠大的情況下。只要在n足夠小的情況下，就算是O(n)的算法也可能會比O(log n)的算法更加高效。另外，一個算法可能在AMD處理器上的速度比在Intel處理器上快。如果你的系統有交換區的話，那么你還要考慮磁盤的性能。唯一可以確定的性能測試途徑是用大小合適的數據來測試和衡量程序的性能和內存使用量。在你所選擇的硬件上來測試這兩種指標，是最合適的方法。

　　Q：如何權衡是用無序的數組還是有序的數組呢?

　　A：有序數組最大的優點在于n比較大的時候，搜索元素所花的時間O(log n)比無序素組所需要的時間O(n)要少很多。有序數組的缺點在于插入的時間開銷比較大(一般是O(n))，因為所有比插入元素大的值都要往后移動。而無序數組的插入時間開銷是常量時間，也就是說，插入的速度和元素的數量無關。下面的代碼片段展示了向有序數組和無序數組插入元素。

　　插入元素到一個無序的數組里

						package bigo; 

						import java.util.Arrays; 

						public class InsertingElementsToArray { 

						    public static void insertUnsortedArray(String toInsert) { 

						        String[ ] unsortedArray = { "A", "D", "C" }; 

						        String[ ] newUnsortedArray = new String[unsortedArray.length + 1]; 

						        System.arraycopy(unsortedArray, 0, newUnsortedArray, 0, 3); 

						        newUnsortedArray[newUnsortedArray.length - 1] = toInsert; 

						        System.out.println(Arrays.toString(newUnsortedArray)); 

						    } 

						    public static void main(String[ ] args) { 

						        insertUnsortedArray("B"); 

						    } 

						}

原文轉自：http://www.importnew.com/871.html

軟件測試 > 測試技術 > 軟件測試工程師職業發展 > 面試精選 >