PHP được xây dựng trong chức năng phức tạp (isAnagramOfPalindrome chức năng)

Question

Tôi đã googling trong 2 giờ qua, và tôi không thể tìm thấy một danh sách các php được xây dựng trong chức năng thời gian và không gian phức tạp. Tôi có vấn đề isAnagramOfPalindrome để giải quyết với độ phức tạp tối đa cho phép sau đây:

expected worst-case time complexity is O(N) 

expected worst-case space complexity is O(1) (not counting the storage required for input arguments). 

trong đó N là độ dài chuỗi đầu vào. Đây là giải pháp đơn giản nhất của tôi, nhưng tôi không biết liệu nó có nằm trong giới hạn phức tạp hay không.

class Solution { 

    // Function to determine if the input string can make a palindrome by rearranging it 
    static public function isAnagramOfPalindrome($S) { 

     // here I am counting how many characters have odd number of occurrences 
     $odds = count(array_filter(count_chars($S, 1), function($var) { 
      return($var & 1); 
     })); 
     // If the string length is odd, then a palindrome would have 1 character with odd number occurrences 
     // If the string length is even, all characters should have even number of occurrences 
     return (int)($odds == (strlen($S) & 1)); 
    } 
} 

echo Solution :: isAnagramOfPalindrome($_POST['input']); 

Bất kỳ ai cũng có ý tưởng tìm loại thông tin này ở đâu?

EDIT

tôi phát hiện ra rằng array_filter có O (N) phức tạp, và count có O (1) phức tạp. Bây giờ tôi cần tìm thông tin trên count_chars, nhưng một danh sách đầy đủ sẽ rất thuận tiện cho các biểu tượng trong tương lai.

EDIT 2

Sau khi một số nghiên cứu về không gian và thời gian phức tạp nói chung, tôi phát hiện ra rằng mã này có O (N) phức tạp thời gian và O (1) không gian phức tạp bởi vì:

Các count_chars sẽ lặp lại N lần (chiều dài đầy đủ của chuỗi đầu vào, cho nó một sự phức tạp bắt đầu của O (N)). Điều này tạo ra một mảng với số lượng trường tối đa giới hạn (26 chính xác, số ký tự khác nhau), và sau đó nó đang áp dụng bộ lọc trên mảng này, có nghĩa là bộ lọc sẽ lặp tối đa 26 lần. Khi đẩy chiều dài đầu vào về phía vô cực, vòng lặp này là không đáng kể và nó được xem như là một hằng số. Đếm cũng áp dụng cho mảng không đổi được tạo ra này, và bên cạnh đó, nó là không đáng kể bởi vì độ phức tạp của hàm count là O (1). Do đó, độ phức tạp của thuật toán là O (N).

Điều này cũng tương tự với độ phức tạp của không gian. Khi tính toán độ phức tạp của không gian, chúng ta không tính đầu vào, chỉ các đối tượng được tạo trong tiến trình. Các đối tượng này là mảng 26 phần tử và biến số đếm, và cả hai đều được coi là hằng số vì kích thước của chúng không thể tăng lên trên điểm này, không quan trọng đầu vào lớn như thế nào. Vì vậy, chúng ta có thể nói rằng thuật toán có độ phức tạp không gian của O (1).

Dù sao, danh sách đó sẽ vẫn có giá trị vì vậy chúng tôi không phải xem bên trong mã nguồn php. :)

Answer 1

Lý do có thể xảy ra khi không bao gồm thông tin này là có khả năng thay đổi cho mỗi bản phát hành, vì các cải tiến được thực hiện/tối ưu hóa cho trường hợp chung.

PHP được xây dựng trên C, Một số chức năng chỉ đơn giản là hàm bao quanh các đối tác c, ví dụ hypot một tìm kiếm google, xem man hypot, trong các tài liệu cho ông Toán lib http://www.gnu.org/software/libc/manual/html_node/Exponents-and-Logarithms.html#Exponents-and-Logarithms

Nguồn thực không cung cấp thông tin tốt hơn https://github.com/lattera/glibc/blob/a2f34833b1042d5d8eeb263b4cf4caaea138c4ad/math/w_hypot.c (Không chính thức, Chỉ cần liên kết dễ dàng)

Chưa kể, Đây chỉ là glibc, Windows sẽ có triển khai khác.Vì vậy, có thậm chí có thể là một O lớn khác nhau cho mỗi hệ điều hành mà PHP được biên dịch trên

Một lý do khác có thể là do nó sẽ nhầm lẫn nhất các nhà phát triển. Hầu hết các nhà phát triển Tôi biết chỉ đơn giản là sẽ chọn một chức năng với "tốt nhất" O lớn

một doesnt tối đa luôn luôn có nghĩa là nó chậm hơn

http://www.sorting-algorithms.com/

Có một prop hình ảnh tốt đẹp của whats xảy ra với một số chức năng , tức là sắp xếp bong bóng là một loại "chậm", Tuy nhiên, đó là một trong những nhanh nhất cho dữ liệu gần như được sắp xếp. Sắp xếp nhanh là những gì nhiều người sẽ sử dụng, điều này thực sự rất chậm đối với dữ liệu gần như được sắp xếp. Big O là trường hợp xấu nhất - PHP có thể quyết định giữa một bản phát hành mà họ nên tối ưu hóa cho một điều kiện nhất định và điều đó sẽ thay đổi O lớn của hàm và không có cách nào dễ dàng để ghi lại điều đó.

Có một phần danh sách ở đây (mà tôi đoán bạn đã thấy)

List of Big-O for PHP functions

nào không liệt kê một số các chức năng PHP phổ biến hơn.

Ví dụ đặc biệt này ....

của nó khá dễ dàng để giải quyết mà không sử dụng được xây dựng trong các chức năng.

Ví dụ mã

function isPalAnagram($string) { 
    $string = str_replace(" ", "", $string); 
    $len = strlen($string); 
    $oddCount = $len & 1; 
    $string = str_split($string); 
    while ($len > 0 && $oddCount >= 0) { 
    $current = reset($string); 
    $replace_count = 0; 
    foreach($string as $key => &$char) { 
     if ($char === $current){ 
     unset($string[$key]); 
     $len--; 
     $replace_count++; 
     continue; 
     } 
    } 
    $oddCount -= ($replace_count & 1); 
    } 

    return ($len - $oddCount) === 0; 

} 

Sử dụng thực tế là không thể có nhiều hơn 1 số lẻ, bạn có thể trở lại sớm từ mảng.

I nghĩ rằng mỏ cũng là thời gian O (N) vì trường hợp xấu nhất của nó là O (N) theo như tôi có thể biết.

thử nghiệm

$a = microtime(true); 
for($i=1; $i<100000; $i++) { 
    testMethod("the quick brown fox jumped over the lazy dog"); 
    testMethod("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"); 
    testMethod("testest"); 
} 
printf("Took %s seconds, %s memory", microtime(true) - $a, memory_get_peak_usage(true)); 

Chạy thử nghiệm sử dụng phần cứng thực sự cũ cách của tôi

Took 64.125452041626 seconds, 262144 memory 

cách của bạn

Took 112.96145009995 seconds, 262144 memory 

Tôi khá chắc chắn rằng con đường của tôi không phải là cách nhanh nhất hoặc.

Tôi thực sự không thể thấy nhiều thông tin cho các ngôn ngữ khác ngoài PHP (ví dụ Java).

Tôi biết rất nhiều bài đăng này là suy đoán về lý do tại sao nó không có ở đó và theres không có nhiều bản vẽ từ các nguồn đáng tin cậy, tôi hy vọng một giải thích một phần lý do tại sao lớn O isnt nó được liệt kê trong trang tài liệu mặc dù