История изменений
Исправление shdown, (текущая версия) :
Не больше и не меньше, чем в Си. Эквивалентная программа gcc с оптимизацией компилируется в O(1), так как суммирование заменяется умножением.
В Си можно рассуждать, поскольку можно рассуждать о худшем случае и «по семантике». Да, оптимизации могут сработать, но это просто плюшки.
По семантике должно быть O(1), так как foldl всегда работает только с головой последовательности, а после foldl эта голова нигде не используется.
А почему ghc без флагов компилирует не «по семантике» и получается O(n)?
[~]-[%] ghc test.hs
[1 of 2] Compiling Main ( test.hs, test.o ) [Missing object file]
[2 of 2] Linking test
[~]-[%] echo 100000000 | ./test
zsh: done echo 100000000 |
zsh: killed ./test
[~]-[%] ghc -O2 test.hs
[1 of 2] Compiling Main ( test.hs, test.o ) [Flags changed]
[2 of 2] Linking test [Objects changed]
[~]-[%] echo 100000000 | ./test
5000000050000000
[~]-[%]
Исходная версия shdown, :
Не больше и не меньше, чем в Си. Эквивалентная программа gcc с оптимизацией компилируется в O(1), так как суммирование заменяется умножением.
В Си можно рассуждать, поскольку можно рассуждать о худшем случае и «по семантике». Да, оптимизации могут сработать, но это просто плюшки.
По семантике должно быть O(1), так как foldl всегда работает только с головой последовательности, а после foldl эта голова нигде не используется.
А почему ghc без флагов компилирует не «по семантике» и получается O(n)?
[~]-[%] ghc primes.hs
[1 of 2] Compiling Main ( primes.hs, primes.o ) [Missing object file]
[2 of 2] Linking primes
[~]-[%] echo 100000000 | ./primes
zsh: done echo 100000000 |
zsh: killed ./primes
[~]-[%] ghc -O2 primes.hs
[1 of 2] Compiling Main ( primes.hs, primes.o ) [Flags changed]
[2 of 2] Linking primes [Objects changed]
[~]-[%] echo 100000000 | ./primes
5000000050000000
[~]-[%]