Back to Repositories

Testing Algorithm Time Complexity Patterns in hello-algo

This test suite evaluates and demonstrates various time complexity patterns in Go algorithms. It systematically tests different algorithmic complexities including constant, linear, quadratic, exponential, logarithmic, and factorial implementations through both iterative and recursive approaches.

Test Coverage Overview

The test suite provides comprehensive coverage of fundamental algorithmic complexity patterns:

Constant time operations (O(1))
Linear complexity operations (O(n))
Quadratic complexity including bubble sort (O(n²))
Exponential complexity with both loop and recursive implementations
Logarithmic operations with iterative and recursive approaches
Factorial complexity implementations

Implementation Analysis

The testing approach utilizes Go’s native testing framework to benchmark different complexity patterns. Each algorithm is tested with a fixed input size (n=8) to demonstrate operation count differences. The implementation showcases both iterative and recursive methods for comparable complexity classes.

Technical Details

Testing Infrastructure:

Go testing package (‘testing’)
Standard output capturing for verification
Dynamic array generation for sorting tests
Systematic operation counting implementation
Consistent input size control

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Clear separation of different complexity classes
Consistent operation counting methodology
Comparative analysis between recursive and iterative implementations
Structured output formatting for result verification
Comprehensive algorithm coverage across complexity spectrum

krahets/hello-algo

zh-hant/codes/go/chapter_computational_complexity/time_complexity_test.go

            
// File: time_complexity_test.go
// Created Time: 2022-12-13
// Author: msk397 ([email protected])

package chapter_computational_complexity

import (
	"fmt"
	"testing"
)

func TestTimeComplexity(t *testing.T) {
	n := 8
	fmt.Println("輸入資料大小 n =", n)

	count := constant(n)
	fmt.Println("常數階的操作數量 =", count)

	count = linear(n)
	fmt.Println("線性階的操作數量 =", count)
	count = arrayTraversal(make([]int, n))
	fmt.Println("線性階（走訪陣列）的操作數量 =", count)

	count = quadratic(n)
	fmt.Println("平方階的操作數量 =", count)
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		nums[i] = n - i
	}
	count = bubbleSort(nums)
	fmt.Println("平方階（泡沫排序）的操作數量 =", count)

	count = exponential(n)
	fmt.Println("指數階（迴圈實現）的操作數量 =", count)
	count = expRecur(n)
	fmt.Println("指數階（遞迴實現）的操作數量 =", count)

	count = logarithmic(n)
	fmt.Println("對數階（迴圈實現）的操作數量 =", count)
	count = logRecur(n)
	fmt.Println("對數階（遞迴實現）的操作數量 =", count)

	count = linearLogRecur(n)
	fmt.Println("線性對數階（遞迴實現）的操作數量 =", count)

	count = factorialRecur(n)
	fmt.Println("階乘階（遞迴實現）的操作數量 =", count)
}