Является ли реализация сортировки вставкой наихудшим вариантом O (n)?

Question

Является ли реализация сортировки вставкой наихудшим вариантом O (n)?

ОБЩИЕ ПРОБЛЕМЫ:

(скопировано из: source )

================= ===

1) перед командой header(.......); не должно быть никакого выхода (т. е. echo.. или HTML-коды].

2) удалить любое пробел (или newline) до и после ?> тегов.

3) ЗОЛОТОЕ ПРАВИЛО! - проверьте, поддерживает ли этот файл php (а также, если вы include другие файлы) UTF8 без кодировки спецификации (а не только UTF-8). Это проблема во многих случаях (потому что кодированный файл UTF8 имеет что-то особенное в начале файла php, которое ваш текстовый редактор не показывает) !!!!!!!!!!!

4) После header(...); вы должны использовать exit;

5) всегда используйте ссылку 301 или 302:

header("location: http://example.com",  true,  301 );  exit;

6) Включить ошибку составление отчетов. И сообщите об ошибке.

7) Если ни одно из вышеизложенных не помогает, используйте перенаправление JAVSCRIPT (однако, сильно не рекомендованный метод), может быть последним шансом в пользовательских случаях ...:

echo ""; exit;


         
            -8

         
         
            insertion-sort time-complexity sorting c++         
         
         
            задан JaMiT            23 August 2019 в 05:49 
         
         
         поделиться


  

      
    

    
   
   
      1 ответ
      

      
         
                     
      

         
         
            
               
                  
                      Неаккуратная терминология привела многих людей к ложным выводам. Это, кажется, пример. 
   существует только один для цикла, включенного здесь, и он работает от 1 до n. 
 
  Да, существует только один цикл, но что это "он", к которому Вы обращаетесь? Я действительно имею в виду, чтобы Вы думали об этом. "Это" должно относиться к циклу? Это соответствовало бы довольно общему, все же неаккуратному, использованию терминологии, но цикл не оценивает к значению. Таким образом, цикл не может на самом деле работать от одного значения до другого. Небрежность может быть пропущена в более простых контекстах, но не в Вашем. 
  Обычно, "это" действительно относилось бы к  контрольная переменная цикла . С простым циклом, как for (int i = 0; i < 10; ++i), существует взаимно-однозначное соответствие между повторениями цикла и оценивает присвоенный контрольной переменной (который является i в моем примере). Таким образом, существует существующая эквивалентность, позволяя один относиться к циклу, когда каждый действительно имеет в виду контрольную переменную. Высказывание, что цикл работает от x до y действительно, означает, что  контрольная переменная  выполнения от x до y, и что  существует одно повторение цикла на значение, присвоенное контрольной переменной . Эта корреспонденция перестала работать в Вашем коде. 
  В Вашем цикле, вещь, которая работает от 1 до n, i. Однако i не увеличен с каждым повторением цикла, таким образом, "это работает от 1 до n",  не  точная оценка Вашего  цикл . Когда i 1, существует до 2 повторений. Это не взаимно-однозначное соответствие между повторениями и значениями i. Как i увеличения, растет расхождение от непосредственного. Каждое значение i потенциально соответствует i+1 повторения, как j количества по сравнению с [1 110] к [1 111]. Общее количество повторений в худшем варианте развития событий для n записей является суммой потенциального количества повторений для каждого значения [1 112]: 2  + 3  + ⋯ + (n+1) = (n²   +   3n)/2. Это - O (n²). 
   Мораль истории: написание компактного, загадочного кода волшебно не изменяет сложность реализовываемого алгоритма. Загадочный код может сделать сложность тяжелее для придавливания, но главное, которое Вы выполнили, делает Ваш код тяжелее для чтения.  
                  
                  
                     
                     0

                  
                  
                  
                     ответ дан                      6 September 2019 в 19:20 
                  
                  поделиться
               
                              
                  
                     
      
                                         
                  
               
            
         
         
               
          Другие вопросы по тегам:          
         insertion-sort time-complexity sorting c++       
        Похожие вопросы:

        
          
                          65 
 Каково худшее реальное злоупотребление macros/pre-processor, с которым Вы когда-либо сталкивались? - 23 May 2017 12:34 
                            64 
 Скрытые функции C++? [закрытый] - 9 September 2009 23:44 
                            51 
 Почему это считают плохой практикой для исключения фигурных скобок? [закрытый] - 19 August 2016 17:07 
                            46 
 Блоги C++, за которыми Вы регулярно следуете? [закрытый] - 17 September 2011 14:57 
                            44 
 Утечки памяти, когда-нибудь в порядке? [закрытый] - 2 October 2011 04:00 
                            38 
 Наиболее ключевые элементы в легком [закрытом] стандарте кодирования C++ - 8 August 2012 01:51 
                            37 
 Потребность в предсказуемом случайном генераторе - 9 April 2016 18:25

score 0 · Answer 1

Неаккуратная терминология привела многих людей к ложным выводам. Это, кажется, пример.

существует только один для цикла, включенного здесь, и он работает от 1 до n.

Да, существует только один цикл, но что это "он", к которому Вы обращаетесь? Я действительно имею в виду, чтобы Вы думали об этом. "Это" должно относиться к циклу? Это соответствовало бы довольно общему, все же неаккуратному, использованию терминологии, но цикл не оценивает к значению. Таким образом, цикл не может на самом деле работать от одного значения до другого. Небрежность может быть пропущена в более простых контекстах, но не в Вашем.

Обычно, "это" действительно относилось бы к контрольная переменная цикла . С простым циклом, как for (int i = 0; i < 10; ++i), существует взаимно-однозначное соответствие между повторениями цикла и оценивает присвоенный контрольной переменной (который является i в моем примере). Таким образом, существует существующая эквивалентность, позволяя один относиться к циклу, когда каждый действительно имеет в виду контрольную переменную. Высказывание, что цикл работает от x до y действительно, означает, что контрольная переменная выполнения от x до y, и что существует одно повторение цикла на значение, присвоенное контрольной переменной . Эта корреспонденция перестала работать в Вашем коде.

В Вашем цикле, вещь, которая работает от 1 до n, i. Однако i не увеличен с каждым повторением цикла, таким образом, "это работает от 1 до n", не точная оценка Вашего цикл . Когда i 1, существует до 2 повторений. Это не взаимно-однозначное соответствие между повторениями и значениями i. Как i увеличения, растет расхождение от непосредственного. Каждое значение i потенциально соответствует i+1 повторения, как j количества по сравнению с [1 110] к [1 111]. Общее количество повторений в худшем варианте развития событий для n записей является суммой потенциального количества повторений для каждого значения [1 112]: 2 + 3 + ⋯ + (n+1) = (n² + 3n)/2. Это - O (n²).

Мораль истории: написание компактного, загадочного кода волшебно не изменяет сложность реализовываемого алгоритма. Загадочный код может сделать сложность тяжелее для придавливания, но главное, которое Вы выполнили, делает Ваш код тяжелее для чтения.