Блог

Я пытаюсь определить Большое О для двух конкурирующих функций. В теории реагирования на элементы (IRT) они называются информационными функциями. Ниже приведены две функции (выраженные в коде R).

 itemInfo1 <- function(theta, b){
        p <- 1 / (1   exp((theta - b)))
        q <- 1 - p
        result <- p * q
        result
}

itemInfo2 <- function(theta, a, b, c, D = 1.7){
    p <- c   (1 - c) / (1   exp(-D * a * (theta - b)))
    q <- 1 - p
    result <- (D^2*a^2*(q/p * ((p - c)/(1-c))^2))  
    result
}
 

Я считаю, что первая функция выполняется в линейном времени и равна O(n). Вторая функция имеет квадратный член, и я полагаю, что после удаления членов более низкого уровня она будет выполняться за квадратичное время, O(n^2).
В моих симуляциях обе функции, по-видимому, выполняются в линейном времени.

 library(microbenchmark)
K <- 10000
a <- runif(K, 0,1.5)
b <- runif(K, -4,4)
c <- runif(K, 0, .5)
L <- seq(from = 10, to = K, by = 10)
mat <- matrix(0, length(L),  2)
for(i in 1:length(L)){
    mat[i,] <- summary(microbenchmark(itemInfo1(0, b[1:(L[i])]), itemInfo2(0, a[1:(L[i])], b[1:(L[i])], c[1:(L[i])]), times=1000L))$mean
}
 

Вторая функция, по-видимому, дороже первой, но графики не предполагают, что она выполняется квадратично.

Мое понимание того, как получить асимптотику большого O для функций, является предварительным, и я ценю реакцию на то, как я мог бы лучше понять время выполнения между этими функциями.

Обозначение Big-O w.r.t. время выполнения используется для указания того, как время выполнения функции масштабируется в зависимости от размера входных данных. В вашем случае размер ваших входных данных вряд ли будет иметь какое-либо значение. Независимо от значений theta , a , b , c и D , каждая функция просто выполняет постоянное количество операций и возвращает результат. Это сделало бы обе функции O(1) . Тот факт, что одна из функций использует квадратный член, не имеет к этому никакого отношения, и на самом деле я думаю exp() , что это будет самая дорогая часть функции.

Технически операции с большими числами займут немного больше времени, но если вы не используете очень большие числа, эта разница будет незначительной.