Back to Repositories

Testing Time Complexity Implementations in hello-algo

This test suite evaluates various time complexity implementations in Go, covering different algorithmic patterns from constant to factorial complexity. It provides comprehensive testing of computational complexity concepts through practical examples like bubble sort, recursion, and array traversal.

Test Coverage Overview

Extensive coverage of time complexity patterns across multiple algorithmic implementations.

Key areas tested include:

Constant, linear, and quadratic time operations
Exponential and logarithmic complexity implementations
Recursive vs iterative approaches
Practical algorithms like bubble sort
Array traversal operations

Implementation Analysis

The test suite employs a systematic approach to verify different complexity patterns using Go’s testing framework. Each complexity category is tested through both theoretical implementations and practical algorithms, with explicit operation counting to validate complexity characteristics.

Testing patterns include:

Direct complexity measurement through operation counting
Comparative analysis of recursive vs iterative implementations
Practical algorithm performance verification

Technical Details

Testing infrastructure:

Go testing framework (testing package)
fmt package for output verification
Custom operation counting mechanisms
Dynamic test data generation
Slice manipulation for array-based tests

Best Practices Demonstrated

The test implementation showcases several testing best practices in Go.

Notable aspects include:

Systematic complexity verification approach
Clear separation of different complexity categories
Comprehensive coverage of both theoretical and practical implementations
Explicit operation counting for verification
Well-structured test organization with clear documentation

krahets/hello-algo

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)
}