Skip to content

Latest commit

 

History

History
112 lines (86 loc) · 2.87 KB

README.md

File metadata and controls

112 lines (86 loc) · 2.87 KB
Raw

Complexity Analysis Library

A Python library for analyzing and visualizing algorithmic complexity. This library helps you determine the time and space complexity of your algorithms through empirical analysis.

Created by Master 1 students at University of El Oued, Algeria (2024/2025) as part of the Advanced Algorithms course.

Features

  • Analyze time complexity of algorithms
  • Compare theoretical vs actual performance
  • Visualize complexity curves
  • Support for common complexity classes:
    • O(1) - Constant
    • O(log n) - Logarithmic
    • O(n) - Linear
    • O(n log n) - Linear-logarithmic
    • O(n²) - Quadratic

Installation

  1. Clone the repository:
git clone <your-repo-url>
cd AdvancedAlgorithmsTP
  1. Create and activate a virtual environment:
python -m venv venv
source venv/bin/activate  # On Windows: .\venv\Scripts\activate
  1. Install dependencies:
pip install -r requirements.txt

Quick Start

1. Basic Usage

from complexity.analyser import ComplexityAnalyzer, LinearComplexity, QuadraticComplexity
from complexity.visualizer import ComplexityVisualizer
import numpy as np

# Generate sample data
sizes = np.array([10, 20, 30, 40, 50])
times = np.array([0.1, 0.4, 0.9, 1.6, 2.5])  # Example execution times

# Create analyzer with complexity functions
analyzer = ComplexityAnalyzer([
    LinearComplexity(),
    QuadraticComplexity()
])

# Find best fitting complexity
best_fit, score = analyzer.get_best_fit(sizes, times)
print(f"Best fitting complexity: {best_fit}")

# Visualize results
visualizer = ComplexityVisualizer(sizes, times)
visualizer.plot(best_fit, title="Algorithm Complexity Analysis")

2. Analyzing Sorting Algorithms

from examples.sort_algos import bubble_sort
import numpy as np

# Generate test data
sizes = [100, 200, 300, 400, 500]
times = []

for n in sizes:
    data = np.random.randint(0, 1000, n)
    start_time = time.time()
    bubble_sort(data)
    times.append(time.time() - start_time)

# Create visualizer
visualizer = ComplexityVisualizer(np.array(sizes), np.array(times))
visualizer.plot(QuadraticComplexity(), title="Bubble Sort Complexity")

3. Custom Complexity Functions

from complexity.analyser import ComplexityFunction

class CustomComplexity(ComplexityFunction):
    def calculate(self, n):
        return n * np.log(n)  # Example: O(n log n)
    
    def __str__(self):
        return "O(n log n)"

# Use custom complexity in analysis
analyzer = ComplexityAnalyzer([CustomComplexity()])

Project Structure

  • complexity/ - Core library code
    • analyser.py - Complexity analysis tools
    • visualizer.py - Plotting and visualization
  • examples/ - Example algorithms
    • search_algos.py - Search algorithms
    • sort_algos.py - Sorting algorithms
  • TPs/ - Jupyter notebooks with analysis

Contributing

Feel free to submit issues and enhancement requests!