Big O Notation Java Eksempel

I dette indlæg præsenterer vi et omfattende Big O Notation Java-eksempel.

1. Introduktion

Asymptotiske notationer bruges til at analysere en algoritmes køretid ved at identificere dens adfærd, når inputstørrelsen for algoritmen øges. Der er seks symboler, der bruges til at karakterisere de relative vækstrater for funktioner:

Symbol	Oversigt
f =Θ(g)	f vokser med samme hastighed som g
f =O(g)	f vokser ikke hurtigere end g
f =Ω(g)	f vokser mindst lige så hurtigt som g
f =o(g)	f vokser langsommere end g
f =ω(g)	f vokser hurtigere end g
f ∼ g	f/g nærmer sig 1

Algoritmeydelsen kan måles baseret på worst-case, best-case og gennemsnit-case. Bachmann-Landau notation er en asymptotisk notation for det værste tilfælde eller loft for vækst for en given funktion. Computerprogrammering bruger denne notation til at klassificere algoritmer i henhold til, hvordan deres computertid eller pladsbehov vokser, efterhånden som inputstørrelsen vokser. Her er notationerne sorteret fra hurtigste til langsomste:

• O(1) – Konstante tidsalgoritmer. Tiden er en konstant mængde tid uanset størrelsen på n. Dette er den hurtigste.
• O(log n) – Logaritmiske tidsalgoritmer – Den vokser i forhold til logaritmen af ​​inputstørrelsen.
• O(n) – Lineære tidsalgoritmer – Den vokser lineært med inputstørrelsen.
• O(n log n) – N Log N Time Algorithms – Den vokser i forhold til n log n af inputstørrelsen.
• O(n^p) – Polynomiske tidsalgoritmer – Disse algoritmer er langsommere end O(n log n ) algoritmer.
• O(k^n) – Eksponentielle tidsalgoritmer – Det vokser i forhold til en vis faktoreksponentiering med inputstørrelsen.
• O(n!) – Faktorielle tidsalgoritmer – Det vokser til inputstørrelsens faktoriale. Dette er den langsomste.

I dette eksempel vil jeg oprette flere metoder og analysere dem med Big O-notationer:O(1) , O(Log n) , O(n) og O(n^2) .

• Summer en heltalsrække ved at tilføje dem alle. Det er O(n) for både tid og rum kompleksitet.
• Summer en heltalsrække ved at bruge formel. Det er O(1) for både tid og rum kompleksitet.
• Find et element fra et sorteret heltalsarray med binær søgealgoritme. Det er O(Log n ) for tidskompleksitet og O(1) for pladskompleksitet.
• Sorter et heltalsarray med indsættelsessorteringsalgoritme. Det er O(n^2 ) for tidskompleksitet og O(1) for pladskompleksitet.

2. Anvendte teknologier

Eksempelkoden i denne artikel blev bygget og kørt ved hjælp af:

• Java 11
• Maven 3.3.9
• Juni 4.12
• Jfreechart 1.5.0
• Eclipse Oxygen

3. Maven Project

I dette trin vil jeg oprette et Maven-projekt, som inkluderer fire klasser for at demonstrere disse notationer. Jeg vil bruge Jfreechart for at vise resultaterne i en linjegraf.

3.1 Afhængigheder

Jeg vil inkludere Junit og Jfreechart i pom.xml .

pom.xml

<project xmlns="http://maven.apache.org/POM/4.0.0"
	xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
	xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
	<modelVersion>4.0.0</modelVersion>
	<groupId>org.jcg.zheng.demo</groupId>
	<artifactId>big-o-demo</artifactId>
	<version>0.0.1-SNAPSHOT</version>

	<properties>
		<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
	</properties>

	<build>
		<sourceDirectory>src</sourceDirectory>
		<plugins>
			<plugin>
				<artifactId>maven-compiler-plugin</artifactId>
				<version>3.8.0</version>
				<configuration>
					<release>11</release>
				</configuration>
			</plugin>
		</plugins>
	</build>
	<dependencies>
		<dependency>
			<groupId>junit</groupId>
			<artifactId>junit</artifactId>
			<version>4.12</version>
		</dependency>
		<dependency>
			<groupId>org.jfree</groupId>
			<artifactId>jfreechart</artifactId>
			<version>1.5.0</version>
		</dependency>
	</dependencies>
</project>

3.2 FileNameConstants

I dette trin vil jeg oprette en FileNameConstants klasse for at definere fire tekstfiler, som gemmer udførelsestiden for hver test. Dataene vil blive brugt til at tegne en linjegraf senere.

FileNameConstants.java

package org.jcg.zheng;

public class FileNameConstants {

	public static final String CONSTANT_TIME = "ConstantTime.csv";
	public static final String LINEAR_TIME = "LinearTime.csv";
	public static final String LOG_TIME = "LogTime.csv";
	public static final String QUADRATIC_TIME = "QuadraticTime.csv";
	public static final String POLY_TIME = "PolyTime.csv";
}

3.3 LineGraphChart

I dette trin vil jeg oprette en LineGraphChart klasse, der strækker sig fra org.jfree.chart.ui.ApplicationFrame . Det vil tegne linjegrafer for givet xy koordinater fra testklasserne. Xy-koordinaterne er inputstørrelsen N vs. den udførelsestid, der blev registreret under testning.

LineGraphChart.java

package org.jcg.zheng;

import java.awt.BorderLayout;
import java.awt.Color;
import java.io.File;
import java.io.IOException;
import java.nio.charset.Charset;
import java.nio.file.Files;
import java.util.HashMap;
import java.util.Map;

import javax.swing.JPanel;

import org.jfree.chart.ChartFactory;
import org.jfree.chart.ChartPanel;
import org.jfree.chart.JFreeChart;
import org.jfree.chart.axis.NumberAxis;
import org.jfree.chart.axis.ValueAxis;
import org.jfree.chart.plot.PlotOrientation;
import org.jfree.chart.plot.XYPlot;
import org.jfree.chart.renderer.xy.StandardXYItemRenderer;
import org.jfree.chart.ui.ApplicationFrame;
import org.jfree.data.xy.XYDataset;
import org.jfree.data.xy.XYSeries;
import org.jfree.data.xy.XYSeriesCollection;

public class LineGraphChart extends ApplicationFrame {

	private static final long serialVersionUID = 8024827403766653799L;

	public static void main(String[] args) {

		final LineGraphChart demo = new LineGraphChart("Big O Notations");
		demo.pack();
		demo.setVisible(true);
	}

	private XYPlot plot;

	public LineGraphChart(String title) {
		super(title);

		final XYDataset dataset1 = createRandomDataset("O(1)", readCoordinates(FileNameConstants.CONSTANT_TIME));
		final JFreeChart chart = ChartFactory.createXYLineChart("Big O Notations", "Input Size", "Value", dataset1,
				PlotOrientation.VERTICAL, true, true, false);
		chart.setBackgroundPaint(Color.white);

		this.plot = chart.getXYPlot();
		this.plot.setBackgroundPaint(Color.lightGray);
		this.plot.setDomainGridlinePaint(Color.white);
		this.plot.setRangeGridlinePaint(Color.white);
		final ValueAxis axis = this.plot.getDomainAxis();
		axis.setAutoRange(true);

		final NumberAxis rangeAxis2 = new NumberAxis("Range Axis 2");
		rangeAxis2.setAutoRangeIncludesZero(false);

		final JPanel content = new JPanel(new BorderLayout());

		final ChartPanel chartPanel = new ChartPanel(chart);
		content.add(chartPanel);

		chartPanel.setPreferredSize(new java.awt.Dimension(700, 500));
		setContentPane(content);

		this.plot.setDataset(1, createRandomDataset("O(n)", readCoordinates(FileNameConstants.LINEAR_TIME)));
		this.plot.setRenderer(1, new StandardXYItemRenderer());
		this.plot.setDataset(2, createRandomDataset("O(logn)", readCoordinates(FileNameConstants.LOG_TIME)));
		this.plot.setRenderer(2, new StandardXYItemRenderer());
		this.plot.setDataset(3, createRandomDataset("O(n^2)", readCoordinates(FileNameConstants.POLY_TIME)));
		this.plot.setRenderer(3, new StandardXYItemRenderer());

	}

	private XYDataset createRandomDataset(final String label, Map<Long, Long> xyCoordinates) {
		XYSeriesCollection dataset = new XYSeriesCollection();
		XYSeries series = new XYSeries(label);

		xyCoordinates.forEach((k, v) -> {
			series.add(k, v);
		});

		dataset.addSeries(series);
		return dataset;
	}

	private Map<Long, Long> readCoordinates(String filename) {
		Map<Long, Long> xyCoordinates = new HashMap<>();
		try {
			File data = new File(filename);
			Files.readAllLines(data.toPath(), Charset.defaultCharset()).forEach(s -> {
				System.out.println(s);
				String[] values = s.split(",");
				xyCoordinates.put(Long.valueOf(values[0]), Long.valueOf(values[1]));
			});
		} catch (IOException e) {
			e.printStackTrace();
		}

		return xyCoordinates;
	}
}

4. Notationer

I computerprogrammering betragtes aritmetiske operationer og adgang til matrixelementer som én operation. Hvis algoritmen har flere operationer, vil det tage længere udførelsestid.

4.1 O(1) Konstant tid

I dette trin vil jeg oprette en ConstantTimeAlgorithm klasse som summerer en heltalsrække fra 1 til N. Den beregner summen via en matematikformel med tre operationer:en multiplikation, en addition og en division. Det samlede antal operationer er konstant 3 uanset inputstørrelsen N. Den samlede hukommelse, der bruges, er tre BigInteger genstande.

I denne notation ignoreres konstanten på grund af dens insignifikans. Denne algoritme har en konstant tids- og rumkompleksitet – O(1) .

ConstantTimeAlgorithm.java

package org.jcg.zheng;

import java.math.BigInteger;

public class ConstantTimeAlgorithm {

	/**
	 * 
	 * O(1) - Calculate the sum from 1 to N via arithmetic series formula
	 */
	public BigInteger sumOfArithmeticSeries_via_formula(long n) {
		return BigInteger.valueOf(n).multiply(BigInteger.valueOf(n + 1)).divide(BigInteger.valueOf(2));
	}

}

4.2 O(n) lineær tid

I dette trin vil jeg oprette en LinearTimeAlgorithm klasse som summerer en heltalsrække fra 1 til N. Den beregner summen ved at lægge alle tallene sammen.

Tilføjelsesoperationen er inde i en for loop, så det samlede antal operationer og det samlede antal objekter vokser, efterhånden som inputstørrelsen vokser – lineær tid – O(n) .

LinearTimeAlgorithm.java

package org.jcg.zheng;

import java.math.BigInteger;

/**
 * Calculate the sum from 1 to N
 *
 */
public class LinearTimeAlgorithm {

	/**
	 * O(n) - Calculate the sum from 1 to N via sum all the numbers
	 */
	public BigInteger sumOfArithmeticSerie_via_add_all(long n) {
		BigInteger sum = BigInteger.valueOf(0);
		for (long i = 1; i <= n; i++) {
			sum = sum.add(BigInteger.valueOf(i));
		}
		return sum;
	}
}

4.3 O(Log n) Logaritmisk tid

I dette trin vil jeg oprette en LogarithmicTime klasse, som søger efter et element fra et sorteret heltalsarray via binær søgealgoritme. Den har to løkker, men den indre løkke reducerer størrelsen til det halve for hver kontrol. Så den samlede operation er Log(n) .

LogarithmicTime.java

package org.jcg.zheng;

public class LogarithmicTimeAlgorithm {

	/**
	 * 
	 * O(log n) - binary search a sorted array. it compares the key value with the
	 * middle element of the array; if they are unequal, the half in which the key
	 * cannot be part of is eliminated
	 */
	public int binarySearchItem(int[] sortedArray, int value) {
		int index = -1;
		int low = 0;
		int high = sortedArray.length;

		while (low <= high) {
			int mid = (low + high) / 2;
			if (sortedArray[mid] < value) {
				low = mid + 1;
			} else if (sortedArray[mid] > value) {
				high = mid - 1;
			} else if (sortedArray[mid] == value) {
				index = mid;
				break;
			}
		}
		return index;
	}

}

4,4 O(n^2) kvadratisk tid

I dette trin vil jeg oprette en QuadraticAlgorithm klasse, som sorterer et heltalsarray via insertation_sort(int[] intArray) . Metoden har to sløjfer.

QuadraticAlgorithm.java

package org.jcg.zheng;

public class QuadraticAlgorithm {

	public void insertation_sort(int numberArray[]) {
		int n = numberArray.length;
		for (int i = 1; i < n; ++i) {
			int position = numberArray[i];
			int j = i - 1;

			while (j >= 0 && numberArray[j] > position) {
				numberArray[j + 1] = numberArray[j];
				j = j - 1;
			}
			numberArray[j + 1] = position;
		}
	}

}

5. JUnit Test

I dette trin vil jeg bruge parameteriseret Junit tests for at fange metodernes udførelsestid og hukommelse, der bruges, når inputstørrelsen vokser. Jeg vil bruge Jfreechart at tegne en tid- og rumkompleksitetsgraf, som viser konstanten O(1) , lineær O(n) , og kvadratisk O(n^2) notationer.

5.1 TestBase

I dette trin vil jeg oprette en TestBase klasse, som starter udførelsestidsuret før og efter hver test. Det gemmer inputstørrelsen og udførelsestiden i en fil for senere at tegne dem i en graf. Den definerer også inputstørrelsesarray, der skal bruges i en parametertest for disse 4 algoritmer.

• setup() – fanger starttidspunktet
• cleanup() – fanger sluttidspunktet og gemmer inputstørrelsen til udførelsestiden i en fil
• setArray() – konstruerer et heltalsarray
• writeFile() – skriver udførelsestiden for hver test
• TEST_SIZE_PARAMETER – er en variabel, der bruges af Parameterized test, så testen kan udføres flere gange, én for hver parameter. Her definerer jeg inputstørrelserne fra 10, 200, 300, 500, 800, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10 , 18000, 19000, til 200000.

TestBase.java

package org.jcg.zheng;

import java.io.FileWriter;
import java.io.IOException;
import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

import org.junit.After;
import org.junit.Before;
import org.junit.Rule;
import org.junit.rules.TestName;

public abstract class TestBase {

	@Rule
	public TestName name = new TestName();

	protected long nSize;

	private Instant startTime;

	private Instant finishTime;

	protected Random randam = new Random();

	protected String filename;

	protected static final List<Object[]> TEST_SIZE_PARAMETER = Arrays
			.asList(new Object[][] { { 10 }, { 200 }, { 300 }, { 500 }, { 800 }, { 1000 }, { 2000 }, { 3000 }, { 4000 },
					{ 5000 }, { 6000 }, { 7000 }, { 8000 }, { 9000 }, { 10000 }, { 11000 }, { 12000 }, { 13000 },
					{ 14000 }, { 15000 }, { 16000 }, { 17000 }, { 18000 }, { 19000 }, { 20000 } });

	@After
	public void cleanup() {
		finishTime = Instant.now();
		long totalTimeInNs = Duration.between(startTime, finishTime).toNanos();

		System.out.printf("\t%s with nSize =%d completed in %d ns\n", name.getMethodName(), nSize, totalTimeInNs);
		if (totalTimeInNs > 0) {
			String line = nSize + "," + totalTimeInNs + "\n";

			writeFile(filename, line);
		}
	}

	@Before
	public void setup() {
		startTime = Instant.now();
	}

	protected int[] setArray(long arraySize) {
		int nSize = (int) arraySize;

		int[] items = new int[nSize];
		for (int i = 0; i < nSize; i++) {
			items[i] = randam.nextInt(10000);
		}
		return items;
	}

	private void writeFile(String filename, String content) {
		try {
			FileWriter fw = new FileWriter(filename, true);
			fw.write(content);
			fw.close();
		} catch (IOException ioe) {
			System.err.println("IOException: " + ioe.getMessage());
		}
	}
}

5.2 ConstantTimeAlgorithmTest

I dette trin vil jeg oprette en ConstantTimeAlgorithmTest for at teste sumOfArithmeticSeries_via_formula . Den strækker sig fra TestBase og udfør testen gentagne gange for forskellige inputstørrelser.

ConstantTimeAlgorithmTest.java

package org.jcg.zheng;

import java.math.BigInteger;
import java.util.Collection;

import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;

@RunWith(Parameterized.class)
public class ConstantTimeAlgorithmTest extends TestBase {

	@Parameterized.Parameters
	public static Collection input() {
		return TEST_SIZE_PARAMETER;
	}

	private ConstantTimeAlgorithm testClass;

	public ConstantTimeAlgorithmTest(long nSize) {
		super();
		this.nSize = nSize;
	}

	@Before
	public void setup() {
		testClass = new ConstantTimeAlgorithm();
		this.filename = FileNameConstants.CONSTANT_TIME;
		super.setup();
	}

	@Test
	public void sumOfArithmeticSeries_via_formula() {
		BigInteger total = testClass.sumOfArithmeticSeries_via_formula(nSize);
		System.out.println("Sum of 1.." + nSize + " = " + total.longValue());
	}

}

Udfør den som Junit-test og indfang output her.

Output

Sum of 1..10 = 55
	sumOfArithmeticSeries_via_formula[0] with nSize =10 completed in 3999500 ns
Sum of 1..200 = 20100
	sumOfArithmeticSeries_via_formula[1] with nSize =200 completed in 999700 ns
Sum of 1..300 = 45150
	sumOfArithmeticSeries_via_formula[2] with nSize =300 completed in 0 ns
Sum of 1..500 = 125250
	sumOfArithmeticSeries_via_formula[3] with nSize =500 completed in 0 ns
Sum of 1..800 = 320400
	sumOfArithmeticSeries_via_formula[4] with nSize =800 completed in 501300 ns
Sum of 1..1000 = 500500
	sumOfArithmeticSeries_via_formula[5] with nSize =1000 completed in 0 ns
Sum of 1..2000 = 2001000
	sumOfArithmeticSeries_via_formula[6] with nSize =2000 completed in 0 ns
Sum of 1..3000 = 4501500
	sumOfArithmeticSeries_via_formula[7] with nSize =3000 completed in 0 ns
Sum of 1..4000 = 8002000
	sumOfArithmeticSeries_via_formula[8] with nSize =4000 completed in 1025900 ns
Sum of 1..5000 = 12502500
	sumOfArithmeticSeries_via_formula[9] with nSize =5000 completed in 0 ns
Sum of 1..6000 = 18003000
	sumOfArithmeticSeries_via_formula[10] with nSize =6000 completed in 0 ns
Sum of 1..7000 = 24503500
	sumOfArithmeticSeries_via_formula[11] with nSize =7000 completed in 0 ns
Sum of 1..8000 = 32004000
	sumOfArithmeticSeries_via_formula[12] with nSize =8000 completed in 0 ns
Sum of 1..9000 = 40504500
	sumOfArithmeticSeries_via_formula[13] with nSize =9000 completed in 0 ns
Sum of 1..10000 = 50005000
	sumOfArithmeticSeries_via_formula[14] with nSize =10000 completed in 0 ns
Sum of 1..11000 = 60505500
	sumOfArithmeticSeries_via_formula[15] with nSize =11000 completed in 3999500 ns
Sum of 1..12000 = 72006000
	sumOfArithmeticSeries_via_formula[16] with nSize =12000 completed in 996800 ns
Sum of 1..13000 = 84506500
	sumOfArithmeticSeries_via_formula[17] with nSize =13000 completed in 0 ns
Sum of 1..14000 = 98007000
	sumOfArithmeticSeries_via_formula[18] with nSize =14000 completed in 0 ns
Sum of 1..15000 = 112507500
	sumOfArithmeticSeries_via_formula[19] with nSize =15000 completed in 0 ns
Sum of 1..16000 = 128008000
	sumOfArithmeticSeries_via_formula[20] with nSize =16000 completed in 999700 ns
Sum of 1..17000 = 144508500
	sumOfArithmeticSeries_via_formula[21] with nSize =17000 completed in 1000100 ns
Sum of 1..18000 = 162009000
	sumOfArithmeticSeries_via_formula[22] with nSize =18000 completed in 0 ns
Sum of 1..19000 = 180509500
	sumOfArithmeticSeries_via_formula[23] with nSize =19000 completed in 0 ns
Sum of 1..20000 = 200010000
	sumOfArithmeticSeries_via_formula[24] with nSize =20000 completed in 999600 ns

5.3 LinerTimeAlgorithmTest

I dette trin vil jeg oprette en LinearTimeAlgorithmTest for at teste sumOfArithmeticSeries_via_add_all . Den strækker sig fra TestBase .

LinearTimeAlgorithmTest.java

package org.jcg.zheng;

import java.math.BigInteger;
import java.util.Collection;

import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;

@RunWith(Parameterized.class)
public class LinearTimeAlgorithmTest extends TestBase {

	@Parameterized.Parameters
	public static Collection input() {
		return TEST_SIZE_PARAMETER;
	}

	private LinearTimeAlgorithm testClass;

	public LinearTimeAlgorithmTest(long nSize) {
		super();
		this.nSize = nSize;
	}

	@Before
	public void setup() {
		testClass = new LinearTimeAlgorithm();
		this.filename = FileNameConstants.LINEAR_TIME;
		super.setup();
	}

	@Test
	public void sumOfArithmeticSeries_via_add_all() {
		BigInteger total = testClass.sumOfArithmeticSerie_via_add_all(nSize);
		System.out.println("Sum of 1.." + nSize + " =" + total.longValue());
	}

}

Udfør den som Junit-test og indfang output her.

Output

Sum of 1..10 =55
	sumOfArithmeticSeries_via_add_all[0] with nSize =10 completed in 4002400 ns
Sum of 1..200 =20100
	sumOfArithmeticSeries_via_add_all[1] with nSize =200 completed in 0 ns
Sum of 1..300 =45150
	sumOfArithmeticSeries_via_add_all[2] with nSize =300 completed in 1999800 ns
Sum of 1..500 =125250
	sumOfArithmeticSeries_via_add_all[3] with nSize =500 completed in 1002100 ns
Sum of 1..800 =320400
	sumOfArithmeticSeries_via_add_all[4] with nSize =800 completed in 999300 ns
Sum of 1..1000 =500500
	sumOfArithmeticSeries_via_add_all[5] with nSize =1000 completed in 998900 ns
Sum of 1..2000 =2001000
	sumOfArithmeticSeries_via_add_all[6] with nSize =2000 completed in 1995300 ns
Sum of 1..3000 =4501500
	sumOfArithmeticSeries_via_add_all[7] with nSize =3000 completed in 999700 ns
Sum of 1..4000 =8002000
	sumOfArithmeticSeries_via_add_all[8] with nSize =4000 completed in 1998500 ns
Sum of 1..5000 =12502500
	sumOfArithmeticSeries_via_add_all[9] with nSize =5000 completed in 1998100 ns
Sum of 1..6000 =18003000
	sumOfArithmeticSeries_via_add_all[10] with nSize =6000 completed in 2999000 ns
Sum of 1..7000 =24503500
	sumOfArithmeticSeries_via_add_all[11] with nSize =7000 completed in 1496400 ns
Sum of 1..8000 =32004000
	sumOfArithmeticSeries_via_add_all[12] with nSize =8000 completed in 1997300 ns
Sum of 1..9000 =40504500
	sumOfArithmeticSeries_via_add_all[13] with nSize =9000 completed in 1497600 ns
Sum of 1..10000 =50005000
	sumOfArithmeticSeries_via_add_all[14] with nSize =10000 completed in 1998100 ns
Sum of 1..11000 =60505500
	sumOfArithmeticSeries_via_add_all[15] with nSize =11000 completed in 3996300 ns
Sum of 1..12000 =72006000
	sumOfArithmeticSeries_via_add_all[16] with nSize =12000 completed in 8997500 ns
Sum of 1..13000 =84506500
	sumOfArithmeticSeries_via_add_all[17] with nSize =13000 completed in 997200 ns
Sum of 1..14000 =98007000
	sumOfArithmeticSeries_via_add_all[18] with nSize =14000 completed in 999700 ns
Sum of 1..15000 =112507500
	sumOfArithmeticSeries_via_add_all[19] with nSize =15000 completed in 1005500 ns
Sum of 1..16000 =128008000
	sumOfArithmeticSeries_via_add_all[20] with nSize =16000 completed in 1003800 ns
Sum of 1..17000 =144508500
	sumOfArithmeticSeries_via_add_all[21] with nSize =17000 completed in 2998600 ns
Sum of 1..18000 =162009000
	sumOfArithmeticSeries_via_add_all[22] with nSize =18000 completed in 1001300 ns
Sum of 1..19000 =180509500
	sumOfArithmeticSeries_via_add_all[23] with nSize =19000 completed in 3999100 ns
Sum of 1..20000 =200010000
	sumOfArithmeticSeries_via_add_all[24] with nSize =20000 completed in 3999500 ns

5.4 Logaritmisk tid O (log n)

I dette trin vil jeg oprette en LogarithmicTimeTest som strækker sig fra TestBase . Den tester binarySearch gentagne gange for forskellige inputstørrelser.

LoogatithmicTimeTest.java

package org.jcg.zheng;

import java.util.Arrays;
import java.util.Collection;

import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;

@RunWith(Parameterized.class)
public class LogarithmicTimeAlgorithmTest extends TestBase {

	@Parameterized.Parameters
	public static Collection input() {
		return TEST_SIZE_PARAMETER;
	}

	private int[] integerArray;

	private int searchingItem;

	private LogarithmicTimeAlgorithm testClass = new LogarithmicTimeAlgorithm();

	public LogarithmicTimeAlgorithmTest(long nSize) {
		super();
		this.nSize = nSize;
	}

	@Before
	public void setup() {
		integerArray = setArray(this.nSize);
		Arrays.sort(integerArray);

		int intSearchItemPo = randam.nextInt((int) this.nSize);
		searchingItem = integerArray[intSearchItemPo];
		this.filename = FileNameConstants.LOG_TIME;
		super.setup();
	}

	@Test
	public void binarySearchItem() {
		int foundKey = testClass.binarySearchItem(integerArray, searchingItem);
		System.out.printf("Searching %d in array[%d], found at position %d\n", searchingItem, integerArray.length,
				foundKey);
	}

}

Udfør binarySearchItem som Junit test og indfang output her.

Output

Searching 3965 in array[10], found at position 4
	binarySearchItem[0] with nSize =10 completed in 2501900 ns
Searching 9319 in array[200], found at position 184
	binarySearchItem[1] with nSize =200 completed in 1001800 ns
Searching 1609 in array[300], found at position 51
	binarySearchItem[2] with nSize =300 completed in 1501400 ns
Searching 6749 in array[500], found at position 334
	binarySearchItem[3] with nSize =500 completed in 499200 ns
Searching 8917 in array[800], found at position 715
	binarySearchItem[4] with nSize =800 completed in 4002000 ns
Searching 3590 in array[1000], found at position 368
	binarySearchItem[5] with nSize =1000 completed in 500900 ns
Searching 4360 in array[2000], found at position 891
	binarySearchItem[6] with nSize =2000 completed in 499200 ns
Searching 7396 in array[3000], found at position 2236
	binarySearchItem[7] with nSize =3000 completed in 2500600 ns
Searching 7483 in array[4000], found at position 3003
	binarySearchItem[8] with nSize =4000 completed in 1500100 ns
Searching 449 in array[5000], found at position 210
	binarySearchItem[9] with nSize =5000 completed in 999700 ns
Searching 3587 in array[6000], found at position 2131
	binarySearchItem[10] with nSize =6000 completed in 1002100 ns
Searching 8680 in array[7000], found at position 6031
	binarySearchItem[11] with nSize =7000 completed in 1999800 ns
Searching 5953 in array[8000], found at position 4774
	binarySearchItem[12] with nSize =8000 completed in 0 ns
Searching 9867 in array[9000], found at position 8877
	binarySearchItem[13] with nSize =9000 completed in 1001400 ns
Searching 2846 in array[10000], found at position 2781
	binarySearchItem[14] with nSize =10000 completed in 996800 ns
Searching 7826 in array[11000], found at position 8590
	binarySearchItem[15] with nSize =11000 completed in 5001700 ns
Searching 5265 in array[12000], found at position 6322
	binarySearchItem[16] with nSize =12000 completed in 1002200 ns
Searching 8071 in array[13000], found at position 10542
	binarySearchItem[17] with nSize =13000 completed in 1997700 ns
Searching 7123 in array[14000], found at position 9953
	binarySearchItem[18] with nSize =14000 completed in 1499300 ns
Searching 8053 in array[15000], found at position 12098
	binarySearchItem[19] with nSize =15000 completed in 1001700 ns
Searching 4520 in array[16000], found at position 7239
	binarySearchItem[20] with nSize =16000 completed in 0 ns
Searching 2803 in array[17000], found at position 4817
	binarySearchItem[21] with nSize =17000 completed in 0 ns
Searching 8273 in array[18000], found at position 14908
	binarySearchItem[22] with nSize =18000 completed in 1000500 ns
Searching 7114 in array[19000], found at position 13430
	binarySearchItem[23] with nSize =19000 completed in 1000500 ns
Searching 9817 in array[20000], found at position 19653
	binarySearchItem[24] with nSize =20000 completed in 0 ns

5,5 kvadratisk tid O(n^2)

I dette trin vil jeg oprette en QuadraticAlgorithmTest som strækker sig fra TestBase .

QuadraticTimeAlgorithmTest.java

package org.jcg.zheng;

import java.util.Collection;

import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;

@RunWith(Parameterized.class)
public class QuadraticAlgorithmTest extends TestBase {

	@Parameterized.Parameters
	public static Collection input() {
		return TEST_SIZE_PARAMETER;
	}

	private int[] integerArray;

	private QuadraticAlgorithm testClass;

	public QuadraticAlgorithmTest(int nSize) {
		super();
		this.nSize = nSize;
	}

	@Test
	public void insertation_sort() {
		testClass.insertation_sort(integerArray);
	}

	@Before
	public void setup() {
		testClass = new QuadraticAlgorithm();
		integerArray = setArray(this.nSize);
		this.filename = FileNameConstants.POLY_TIME;
		super.setup();
	}

}

Udfør insertation_sort som Junit test og indfang output her.

Output

	insertation_sort[0] with nSize =10 completed in 0 ns
	insertation_sort[1] with nSize =200 completed in 999300 ns
	insertation_sort[2] with nSize =300 completed in 1500100 ns
	insertation_sort[3] with nSize =500 completed in 2998200 ns
	insertation_sort[4] with nSize =800 completed in 4497500 ns
	insertation_sort[5] with nSize =1000 completed in 11499700 ns
	insertation_sort[6] with nSize =2000 completed in 1501400 ns
	insertation_sort[7] with nSize =3000 completed in 2000200 ns
	insertation_sort[8] with nSize =4000 completed in 5500000 ns
	insertation_sort[9] with nSize =5000 completed in 5498400 ns
	insertation_sort[10] with nSize =6000 completed in 10500400 ns
	insertation_sort[11] with nSize =7000 completed in 12502300 ns
	insertation_sort[12] with nSize =8000 completed in 16000100 ns
	insertation_sort[13] with nSize =9000 completed in 20497600 ns
	insertation_sort[14] with nSize =10000 completed in 27997800 ns
	insertation_sort[15] with nSize =11000 completed in 33000300 ns
	insertation_sort[16] with nSize =12000 completed in 25995200 ns
	insertation_sort[17] with nSize =13000 completed in 40053400 ns
	insertation_sort[18] with nSize =14000 completed in 61015800 ns
	insertation_sort[19] with nSize =15000 completed in 44512800 ns
	insertation_sort[20] with nSize =16000 completed in 41013700 ns
	insertation_sort[21] with nSize =17000 completed in 44513200 ns
	insertation_sort[22] with nSize =18000 completed in 56512500 ns
	insertation_sort[23] with nSize =19000 completed in 60998100 ns
	insertation_sort[24] with nSize =20000 completed in 84023900 ns

5.6 Big O Test Suite

I dette trin vil jeg oprette en BigOTestSuite klasse, som inkluderer ConstantTimeAlgorithmTest , LinearTimeAlgorithmTest , LogarithmicTimeAlgorithmTest og QuadraticAlgorithmTest klasse. Den vil tegne en graf for at vise udførelsestiden relateret til inputstørrelsen for hver algoritme.

BigOTestSuite.java

package org.jcg.zheng;

import org.junit.AfterClass;
import org.junit.runner.RunWith;
import org.junit.runners.Suite;
import org.junit.runners.Suite.SuiteClasses;

@RunWith(Suite.class)
@SuiteClasses({ ConstantTimeAlgorithmTest.class, LinearTimeAlgorithmTest.class, LogarithmicTimeAlgorithmTest.class,
		QuadraticAlgorithmTest.class })
public class BigOTestSuite {

	 
	@AfterClass
	public static void tearDown() {		
		LineGraphChart xyChart = new LineGraphChart("Big O Notations");
		xyChart.setVisible(true);
		xyChart.pack();
		System.out.println("DONE");
	}

}

Ved afslutningen af ​​testen vil den tegne en linjegraf med 4 linjer med forskellig farve:

• O(1) – rød linje, det er en næsten parallel linje med X-aksen.
• O(log n) – grøn linje, den vokser langsommere end den lineære linje.
• O(n) – blå linje, den vokser lidt hurtigere end logaritmelinjen.
• O(n^2) – gul linje, den vokser hurtigt, når inputstørrelsen vokser.

6. Big O Notation Java Eksempel – Resumé

I dette eksempel forklarede vi, hvad denne notation er, og skabte fire metoder og forklarede deres tids- og rumeffektivitet, når inputstørrelsen vokser.

Som du har set, er O(n^2) vokser hurtigt, når inputstørrelsen vokser. Udviklere bør være forsigtige med en algoritme, hvor denne notation er langsommere end O(n^2) . Klik her for en komplet liste over denne analyse for de mest kendte sorteringsalgoritmer af Eric Rowel.

Som Java-udvikler bør vi analysere algoritmen for at sikre, at den opfylder forretningskravene og den potentielle vækst.

Dette Big O Notation Java-eksempel består af et Maven-projekt, som viser tids- og rumkompleksitetsanalyse via disse notationer.