Как оценить затраченное время? (темпы роста)

Начнем с (4). Использование$O$обозначения здесь очень неаккуратны, но что здесь имеется в виду, когда говорят, что временная сложность алгоритма равна$O(N^2)$заключается в том, что требуемое время примерно пропорционально$N^2$. То есть существует некоторая постоянная$k$так что время, необходимое для обработки ввода размера$N$примерно$kN^2$. В этой задаче вам говорят, что когда$N=1000$, время$10$секунд, так что$k(1000)^2=10$. Вы могли бы решить это для$k$, если уж очень хотелось, да ненужно: хочешь$kN^2$когда$N=1,000,000$, и$1,000,000=1000^2$, так что вы хотите

$$k(1,000,000)^2= k(1000)^2(1000)^2=10(1000)^2=10,000,000\;,$$ с $k(1000)^2=10$. Другими словами, в (4) ваш алгоритм займет около десяти миллионов секунд, что составляет чуть меньше трети года.

В (2) вам говорят, что алгоритм занимает около$kN$секунд, чтобы справиться с проблемой размера$N$, И ты знаешь это$1000k=10$. Я позволю вам попытаться решить это и (5) использовать мое решение для (4) в качестве модели; вы должны получить чуть более двух и трех четвертей часов для (2) и более трех столетий для (5).

Теперь давайте посмотрим на (1): он говорит, что приблизительное время работы на входе размера$N$является$k\log N$для некоторой константы$k$, и нам говорят, что$k\log 1000=10$. Вам разрешено приближение$\log 1000\approx 10$, так что у нас есть$10k=10$, или$k=1$. Таким образом, приблизительное время работы$N=1,000,000$является

$$k\log 1,000,000=\log 1,000,000\approx 20$$ секунды.

(3) выглядит самым грязным, но не сложнее остальных: примерное время работы на входе размера$N$является$kN\log N$, и вам дано это$k(1000)\log 1000=10$. Еще раз вы можете либо решить для$k$и подключи$N=1,000,000$или использовать данную точку данных более прямым способом, как я сделал с (4); вы должны получить продолжительность чуть более пяти с половиной часов.