이런저런 IT 이야기

Big O 표기법을 그래프로 표현 본문

Algorithm

Big O 표기법을 그래프로 표현

이런저런 IT 이야기 2023. 5. 24. 10:31
반응형

 

  • 우선 그래프를 그리기 위해서 D3.js 라이브러리 파일을 다운로드 받아야 합니다. 아래 링크에서 받으세요

        https://d3js.org/

  • HTML코드입니다.
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <script src="dist/d3.min.js"></script>
</head>

<body>
    <script>
        // D3.js를 이용한 선형 그래프 그리기
        const data = [];
        const maxN = 10;

        // 시간 복잡도 O(1)인 알고리즘 예시
        function algorithm1(n) {
            // O(1) 수행시간
            return n;
        }

        // 시간 복잡도 O(n)인 알고리즘 예시
        function algorithm2(n) {
            // O(n) 수행시간
            let sum = 0;
            for (let i = 0; i < n; i++) {
                sum += i;
            }
            return sum;
        }

        // 시간 복잡도 O(n^2)인 알고리즘 예시
        function algorithm3(n) {
            // O(n^2) 수행시간
            let sum = 0;
            for (let i = 0; i < n; i++) {
                for (let j = 0; j < n; j++) {
                    sum += i + j;
                }
            }
            return sum;
        }

        for (let n = 1; n <= maxN; n++) {
            data.push({
                n: n,
                time1: algorithm1(n),
                time2: algorithm2(n),
                time3: algorithm3(n),
            });
        }

        const svgWidth = 600;
        const svgHeight = 400;
        const margin = { top: 20, right: 20, bottom: 30, left: 50 };
        const chartWidth = svgWidth - margin.left - margin.right;
        const chartHeight = svgHeight - margin.top - margin.bottom;

        const svg = d3
            .select("body")
            .append("svg")
            .attr("width", svgWidth)
            .attr("height", svgHeight);

        const chart = svg
            .append("g")
            .attr("transform", `translate(${margin.left}, ${margin.top})`);

        const xScale = d3
            .scaleLinear()
            .domain([0, maxN])
            .range([0, chartWidth]);

        const yScale = d3
            .scaleLinear()
            .domain([0, d3.max(data, (d) => d3.max([d.time1, d.time2, d.time3]))])
            .range([chartHeight, 0]);

        const xAxis = d3.axisBottom(xScale);
        const yAxis = d3.axisLeft(yScale);

        chart.append("g").attr("transform", `translate(0, ${chartHeight})`).call(xAxis);
        chart.append("g").call(yAxis);

        const line1 = d3
            .line()
            .x((d) => xScale(d.n))
            .y((d) => yScale(d.time1));

        const line2 = d3
            .line()
            .x((d) => xScale(d.n))
            .y((d) => yScale(d.time2));

        const line3 = d3
            .line()
            .x((d) => xScale(d.n))
            .y((d) => yScale(d.time3));

        chart
            .append("path")
            .datum(data)
            .attr("fill", "none")
            .attr("stroke", "red")
            .attr("stroke-width", 2)
            .attr("d", line1);

        chart
            .append("path")
            .datum(data)
            .attr("fill", "none")
            .attr("stroke", "green")
            .attr("stroke-width", 2)
            .attr("d", line2);

        chart
            .append("path")
            .datum(data)
            .attr("fill", "none")
            .attr("stroke", "blue")
            .attr("stroke-width", 2)
            .attr("d", line3);


    </script>
</body>

</html>

위 코드의 화면은 아래처럼 보입니다.

 

그래프는 Big O 표기법으로 알고리즘의 시간 복잡도를 나타내고 있습니다. 각 알고리즘의 수행시간이 입력 크기에 대해 어떻게 증가하는지를 시각적으로 보여주는 것이 목적입니다.

알고리즘1의 경우, 수행시간이 입력 크기 n에 대해 상수 시간으로 일정하게 유지되므로 O(1) 시간 복잡도를 가집니다.

알고리즘2의 경우, 수행시간이 입력 크기 n에 비례하여 선형으로 증가하므로 O(n) 시간 복잡도를 가집니다.

알고리즘3의 경우, 수행시간이 입력 크기 n의 제곱에 비례하여 증가하므로 O(n^2) 시간 복잡도를 가집니다.

따라서, 위 그래프는 각 알고리즘의 시간 복잡도를 Big O 표기법으로 나타낸 것입니다.

반응형
저작자표시 변경금지

'Algorithm' 카테고리의 다른 글

Programming Challenges #33  (0) 2023.05.24
Programming Challenges #32  (0) 2023.05.24
알고리즘의 시간 복잡도를 나타내는 표기 방법  (0) 2023.05.24
휴리스틱 알고리즘  (0) 2023.05.23
NP-hard Problems  (0) 2023.05.23
'Algorithm' Related Articles more