Instalar com Codex ou Claude Copie este prompt, cole no Codex, Claude ou outro assistente e deixe que ele revise a página da skill e instale para você.
Um comando direto ignora o prompt de revisão. Verifique a origem antes de executá-lo.
# R implementation of formal I/O specification
define_algorithm_io <-function(){list(
input =list(
data
params
models
output
estimate
se
vcov
converged
iterations
complexity
time
space
iterations
Matrix inversion: $O(n^3)$ (same as multiplication)
# Complexity analysis helper
analyze_complexity <-function(f, n_values =c(100,500,1000,5000)){
times <- sapply(n_values,function(n){
system.time(f(n))[["elapsed"]]})# Fit log-log regression to estimate complexity
fit <- lm(log(times)~log(n_values))
estimated_power <- coef(fit)[2]list(
times = data.frame(n = n_values, time = times),
estimated_complexity = paste0("O(n^",round(estimated_power,2),")"),
power = estimated_power
)}
Statistical Algorithm Complexities
Algorithm
Time
Space
OLS
O(np² + p³)
O(np)
Logistic (Newton)
O(np² + p³) per iter
O(np)
Bootstrap (B reps)
O(B × base)
O(n)
MCMC (T iters)
O(T × per_iter)
O(n + T)
Cross-validation (K)
O(K × base)
O(n)
Random forest
O(n log n × B × p)
O(n × B)
Template for Analysis
TIME COMPLEXITY:
- Initialization: O(...)
- Per iteration: O(...)
- Total (T iterations): O(...)
- Convergence typically in T = O(...) iterations
SPACE COMPLEXITY:
- Data storage: O(n × p)
- Working memory: O(...)
- Output: O(...)
Convergence Analysis
Types of Convergence
Finite termination: Exact solution in finite steps
CONVERGENCE:
- Type: [Linear/Superlinear/Quadratic]
- Rate: [Expression]
- Conditions: [What must hold]
- Stopping criterion: [When to stop]
- Typical iterations: [Order of magnitude]
Optimization Algorithms
Gradient-Based Methods
ALGORITHM: Gradient Descent
INPUT: f (objective), ∇f (gradient), x₀ (initial), η (step size), ε (tolerance)
OUTPUT: x* (minimizer)
1. k ← 0
2. WHILE ‖∇f(xₖ)‖ > ε:
2.1 xₖ₊₁ ← xₖ - η∇f(xₖ)
2.2 k ← k + 1
3. RETURN xₖ
COMPLEXITY: O(iterations × gradient_cost)
CONVERGENCE: Linear with rate (1 - η·μ) for μ-strongly convex f
Newton's Method
ALGORITHM: Newton-Raphson
INPUT: f, ∇f, ∇²f, x₀, ε
OUTPUT: x*
1. k ← 0
2. WHILE ‖∇f(xₖ)‖ > ε:
2.1 Solve ∇²f(xₖ)·d = -∇f(xₖ) for direction d
2.2 xₖ₊₁ ← xₖ + d
2.3 k ← k + 1
3. RETURN xₖ
COMPLEXITY: O(iterations × p³) for p-dimensional
CONVERGENCE: Quadratic near solution
EM Algorithm Template
ALGORITHM: Expectation-Maximization
INPUT: Data Y, model parameters θ₀, tolerance ε
OUTPUT: MLE θ̂
1. θ ← θ₀
2. REPEAT:
2.1 E-STEP: Compute Q(θ'|θ) = E[log L(θ'|Y,Z) | Y, θ]
2.2 M-STEP: θ_new ← argmax_θ' Q(θ'|θ)
2.3 Δ ← |θ_new - θ|
2.4 θ ← θ_new
3. UNTIL Δ < ε
4. RETURN θ
CONVERGENCE: Monotonic increase in likelihood
Linear rate near optimum
Bootstrap Algorithms
Nonparametric Bootstrap
ALGORITHM: Nonparametric Bootstrap
INPUT: Data X of size n, statistic T, B (number of replicates)
OUTPUT: SE estimate, CI
1. FOR b = 1 to B:
1.1 Draw X*_b by sampling n observations with replacement from X
1.2 Compute T*_b = T(X*_b)
2. SE_boot ← SD({T*_1, ..., T*_B})
3. CI_percentile ← [quantile(T*, 0.025), quantile(T*, 0.975)]
4. RETURN (SE_boot, CI_percentile)
COMPLEXITY: O(B × cost(T))
NOTES: B ≥ 1000 for SE, B ≥ 10000 for percentile CI
Parametric Bootstrap
ALGORITHM: Parametric Bootstrap
INPUT: Data X, parametric model M, B replicates
OUTPUT: SE estimate
1. Fit θ̂ = MLE(X, M)
2. FOR b = 1 to B:
2.1 Generate X*_b ~ M(θ̂)
2.2 Compute θ̂*_b = MLE(X*_b, M)
3. SE_boot ← SD({θ̂*_1, ..., θ̂*_B})
4. RETURN SE_boot
Numerical Stability Notes
Common Issues
Overflow/Underflow: Work on log scale
Cancellation: Reformulate subtractions
Ill-conditioning: Use regularization or pivoting
Convergence: Add damping or line search
Stability Techniques
# Log-sum-exp trick
log_sum_exp <-function(x){
max_x <-max(x)
max_x +log(sum(exp(x - max_x)))}# Numerically stable variance
stable_var <-function(x){
n <-length(x)
m <- mean(x)sum((x - m)^2)/(n -1)# One-pass with correction}
