样本的时间复杂度是多少？

Question

使用默认参数，

sample

的时间复杂度是多少？ IE。

sample(1:N)

的运行时间如何随N增长？

示例文档位于此处，但未指定时间复杂度。

Answer 1

在我的测试中，一旦 N > 30,000，看起来呈线性，其中 N 中 10 个样本的平均采样时间约为每个样本 0.5 微秒。对于较低的 N 似乎存在开销，这使得每个样本的时间更长。

sample_range = 10^seq(2, 7, 0.05)

take_sample <- function(n) {
    test <- microbenchmark::microbenchmark(
              sample(n, 10), times = 100, unit = "microseconds")
    avg = mean(test$time)
    data.frame(n, avg)
  }

# takes about 20 sec on my machine
sample_results <- lapply(sample_range, take_sample)

然后显示这些结果：

library(tidyverse)
bind_rows(sample_results) |>
  mutate(microsec_per_range = avg / n) |>
  ggplot(aes(n, microsec_per_range)) +
  geom_point() +
  expand_limits(y = 0) +
  scale_x_log10(breaks = c(10^(2:7), 3*10^(2:7)),
                labels = scales::comma_format()) +
  scale_y_continuous(breaks = c(0, 0.3, 1, 3, 10, 30, 100),
                     trans = scales::pseudo_log_trans(sigma = 0.1))