Я думаю, что вы путаетесь между тета-нотацией и большой буквой О.
Тета-нотация определяет приблизительную оценку времени работы алгоритма, в то время как Big O-нотация определяет наихудшее время работы алгоритма.
Метод, который вы упомянули выше, используется для вычисления тэты, а не большой О. Большой O из вышеупомянутой проблемы может быть O (n ^ 4), O (n ^ 5), O (n ^ 6) и так далее ... все правильные значения. Но для тэты только тэта (n ^ 3) верна.
Да.
C ++ с реализацией интеллектуального указателя будет собирать мусор, когда счетчик ссылок интеллектуального указателя стремится к нулю.
У вас есть сборка мусора. Вы не строили его сами.
Сборка мусора требует, чтобы переменные-указатели отмечались специальным образом, чтобы среда выполнения могла их идентифицировать и использовать для сбора мусора. Он не имеет ничего общего с интерпретацией / компиляцией, но вместо этого требует специального времени выполнения и сохранения дополнительных данных для каждой переменной.
Что ж, языки .NET (которые излучают в IL - C #, VB.NET, MC ++ и т. Д.) Не интерпретируются (особенно если вы используете NGEN) - и имеют полную сборку мусора.
Аналогично, Ява.
Новый C ++ 0x включает функции, упрощающие реализацию сборки мусора. См., Например, это интервью .
Objective-C 2 теперь имеет сборку мусора, и есть библиотеки сбора мусора, доступные также для C ++.
Я думаю, что это возможно, если есть язык, который позволяет вам проверять объекты, чтобы вы могли обойти дерево объектов.
Для фактической реализации на скомпилированном языке, в данном случае C и / или C ++, см. Boehm GC на http://www.hpl.hp.com/personal/ Hans_Boehm / gc /
В Haskell есть сборка мусора, независимо от того, скомпилирована она в машинный код или интерпретирована.