Использование ptrdiff_t

Question

Использование ptrdiff_t

Конечно, числа Фибоначчи могут быть вычислены в O (n), применяя формулу Бине:

from math import floor, sqrt

def fib(n):                                                     
    return int(floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))+0.5))

Как отмечают комментаторы, это не O (1), а O (n) из-за 2**n. Также разница в том, что вы получаете только одно значение, а при рекурсии вы получаете все значения Fibonacci(n) до этого значения.

4

c language-lawyer

задан AShelly 26 March 2019 в 17:02

2 ответа

Другие вопросы по тегам:
c language-lawyer

Похожие вопросы:

65
Каково худшее реальное злоупотребление macros/pre-processor, с которым Вы когда-либо сталкивались? - 23 May 2017 12:34

55
Какие важные понятия в Си, которые вы не узнали от своих учителей? [закрыто] - 6 September 2017 17:22

51
Почему это считают плохой практикой для исключения фигурных скобок? [закрытый] - 19 August 2016 17:07

48
Скрытые возможности C - 25 September 2017 20:52

44
Утечки памяти, когда-нибудь в порядке? [закрытый] - 2 October 2011 04:00

39
Форматирование если Операторы - 17 January 2014 19:45

31
Когда сборка происходит быстрее, чем C? - 3 January 2018 15:58

score 0 · Answer 1

Из спецификации (раздел 7.20.3)

Его значение, определяемое реализацией, должно быть равным или больше по величине (абсолютное значение) чем соответствующее значение, указанное ниже

_{[Emphasis mine]}

Таким образом, упомянутые значения являются только минимальными значениями. Реализация может иметь большие ограничения. Я ожидал бы, что ptrdiff_t будет длиной слова целевой платформы (то есть 64-битного типа 64-битных систем).

И обратите внимание, что size_t является целым типом без знака , а ptrdiff_t является целым типом со знаком . Этот тип подразумевает, что не все значения size_t могут быть представлены ptrdiff_t.

score 0 · Answer 2

Это, похоже, проблема в самом стандарте C.

Как вы заметили, 6.5.6 Аддитивные операторы , пункт 9 , в частности, гласит:

Когда вычитаются два указателя, оба должны указывать к элементам одного и того же объекта массива или одному последнему элементу объекта массива; Результатом является разница индексов двух элементов массива. Размер результата определяется реализацией, а его тип (целочисленный тип со знаком) определяется как ptrdiff_t в заголовке <stddef.h>. Если результат не может быть представлен в объекте этого типа, поведение не определено. Другими словами, если выражения P и Q указывают соответственно на i -й и j -й элементы массива, выражение (P)-(Q) имеет значение i-j [1123 ] при условии, что значение соответствует объекту типа ptrdiff_t . ...

В стандарте C, похоже, нет гарантии, что вы можете представить разницу двух указателей в ptrdiff_t.

Реально, это будет означать, что ptrdiff_t должно быть больше, чем size_t. size_t должен покрывать только величину в фиксированном количестве битов. ptrdiff_t должен охватывать как величину, так и направление. Если sizeof( size_t ) == sizeof( ptrdiff_t ), то нет гарантии, что неопределенное поведение в 6.5.6p9 не будет вызвано.