Алгоритмы поиска и сортировки

  • Published on
    05-Apr-2017

  • View
    76

  • Download
    6

Embed Size (px)

Transcript

<ul><li><p>.</p><p>*</p></li><li><p> c</p><p>*</p></li><li><p> , .</p><p>*</p></li><li><p> , .</p><p>*</p></li><li><p> - , . </p><p>*</p></li><li><p> , , , .</p><p>*</p></li><li><p> , . . . , O(log n) . </p><p>*</p></li><li><p>*</p></li><li><p>f(n) O(g(n))f g ( ) f(n) (g(n))f g ( ) f(n) (g(n))f g </p><p>*</p></li><li><p> O</p><p>*</p></li><li><p>*</p></li><li><p>*</p></li><li><p> , -</p><p>*</p></li><li><p> 134871519</p><p>*</p></li><li><p> 1 1970 .long startTime = System.currentTimeMillis(); ; ; ;long endTime = System.currentTimeMillis();long workTime = endTime startTime;</p><p>*</p></li><li><p>*</p></li><li><p> ( , ) , ( ), .</p><p>*</p></li><li><p> () () ( ) (), . O(log n)Arrays.binarySearch(mas)</p><p>*</p></li><li><p>*</p></li><li><p> .int mid = (left + right) / 2; int mid = left + (right - left) / 2;</p><p>*</p></li><li><p> 31.</p><p>27 &lt; 31 </p><p> left = mid + 1;</p><p>*</p></li><li><p>35 &gt; 31 </p><p> right = mid - 1;</p><p>*</p></li><li><p>*</p></li><li><p>*</p></li><li><p>*</p></li><li><p> . , , , , </p><p>*</p></li><li><p> ; ( 20 100 );</p><p>*</p></li><li><p> ; ; ;</p><p>*</p></li><li><p> , , . (.stability) . </p><p>*</p></li><li><p> . , . . , , .</p><p>*</p></li><li><p> (.Bubble sort) , . </p><p> : O(n2).. </p><p>*</p></li><li><p> O(n2) O(n) O(n2) O (1) </p><p>*</p></li><li><p>*</p></li><li><p>*</p></li><li><p> : ( , ) , </p><p>, .</p><p>*</p></li><li><p>*</p></li><li><p>*</p></li><li><p>*</p></li><li><p> . Insertion sort, , . : O(n2).. .</p><p>*</p></li><li><p>*</p></li><li><p>*</p></li><li><p> : , ; , ; ( , );</p><p>*</p></li><li><p> ;O(1) , . : ( ).</p><p>*</p></li><li><p>*</p></li><li><p>*</p></li><li><p>*</p></li><li><p> (Shell sort) , . , , . .</p><p>*</p></li><li><p>*</p></li><li><p>QuicksortQuicksort - , , . </p><p>*</p></li><li><p> . , . 1960.</p><p>*</p></li><li><p> (Quicksort) O(n log n) , O (n2) ; </p><p>*</p></li><li><p>Quicksort</p><p>*</p></li><li><p>*</p></li><li><p>*</p></li><li><p>Timsort Timsort , , 2002 . Timsort Python,OpenJDK7 AndroidJDK 1.5. </p><p>*</p></li><li><p>Timsort , . Timsort .</p><p>*</p></li><li><p> , , . 1981 . , O(nlogn). </p><p>*</p></li><li><p> , O(n), , , .</p><p>*</p></li><li><p>*</p></li><li><p> - O(n log n). O(n) O(n log n). O(n). O(n+k). O(n+k) ( ) O(n) (k)</p><p> ()</p><p>*</p></li><li><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p><p>*</p></li></ul>

Recommended

View more >