Rumah  >  Artikel  >  Java  >  Bagaimana untuk mengira kerumitan masa dalam java

Bagaimana untuk mengira kerumitan masa dalam java

下次还敢
下次还敢asal
2024-05-01 18:54:39293semak imbas

Kerumitan masa mengukur kecekapan algoritma dan mewakili tingkah laku asimptotik masa yang diperlukan untuk pelaksanaan algoritma. Notasi O besar digunakan dalam Java untuk mewakili kerumitan masa yang biasa ialah: O(1), O(n), O(n^2), O(log n). Langkah-langkah untuk mengira kerumitan masa sesuatu algoritma termasuk: menentukan operasi asas, mengira bilangan operasi asas, meringkaskan masa operasi asas dan memudahkan ungkapan. Contohnya, algoritma carian linear yang merentasi n elemen mempunyai kerumitan masa O(n), dan masa carian meningkat secara linear apabila saiz senarai bertambah.

Bagaimana untuk mengira kerumitan masa dalam java

Kaedah pengiraan kerumitan masa dalam Java

Apakah kerumitan masa?

Kerumitan masa ialah ukuran kecekapan algoritma, yang menerangkan masa yang diperlukan untuk algoritma dilaksanakan apabila jumlah data input berbeza-beza.

Bagaimana untuk mengira kerumitan masa di Jawa?

Kerumitan masa di Jawa biasanya dinyatakan dalam tatatanda O besar, yang mewakili kelakuan asimptotik sesuatu fungsi apabila bilangan input menghampiri infiniti. Berikut ialah beberapa perwakilan kerumitan masa biasa:

  • O(1): Masa malar, kerumitan masa adalah malar tanpa mengira saiz input.
  • O(n): Masa linear, kerumitan masa berkembang secara berkadar dengan saiz input n.
  • O(n^2): Masa segi empat sama, kerumitan masa berkembang secara berkadar dengan kuasa dua saiz input n.
  • O(log n): Masa logaritma, kerumitan masa berkembang secara logaritma dengan saiz input n.

Bagaimana untuk mengira kerumitan masa algoritma tertentu?

Langkah-langkah untuk mengira kerumitan masa algoritma tertentu adalah seperti berikut:

  1. Kenal pasti operasi asas: Kenal pasti operasi asas yang paling kerap dilakukan dalam algoritma.
  2. Kira bilangan operasi asas: Tentukan bilangan kali setiap operasi asas dilakukan untuk saiz input yang diberikan.
  3. Pengagregatan masa operasi asas: Darabkan kerumitan masa setiap operasi asas dengan bilangan pelaksanaannya dan tambahkannya bersama.
  4. Ringkaskan ungkapan: Singkirkan faktor malar dan kekalkan istilah tertib tertinggi yang berkaitan dengan saiz input.

Contoh:

Pertimbangkan algoritma carian linear berikut untuk mencari elemen dalam senarai:

<code class="java">public int linearSearch(List<Integer> list, int target) {
  for (int i = 0; i < list.size(); i++) {
    if (list.get(i) == target) {
      return i;
    }
  }
  return -1;
}</code>
  1. Kendalian asas: Lelaran pada setiap elemen dalam senarai.
  2. Bilangan operasi asas: n, dengan n ialah saiz senarai.
  3. Ringkaskan masa operasi asas: n * 1 = n
  4. Ringkaskan ungkapan: Kerumitan masa ialah O(n).

Oleh itu, kerumitan masa bagi algoritma carian linear ini ialah O(n), yang bermaksud bahawa apabila saiz senarai bertambah, masa yang diperlukan untuk carian akan meningkat secara linear.

Atas ialah kandungan terperinci Bagaimana untuk mengira kerumitan masa dalam java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn